Description

There is an undirected graph with n nodes, where each node is numbered between 0 and n – 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).

• There are no parallel edges (graph[u] does not contain duplicate values).

• If v is in graph[u], then u is in graph[v] (the graph is undirected).

• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

 

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

 

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]

Output: true

Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

 

Constraints:

• graph.length == n

• 1 <= n <= 100

• 0 <= graph[u].length < n

• 0 <= graph[u][i] <= n - 1

• graph[u] does not contain u.

• All the values of graph[u] are unique.

• If graph[u] contains v, then graph[v] contains u.

Thinking

Initially, I really have no idea. After getting a hint about using DFS and coloring, I instantly got the idea of the solution. Basically, we can use DFS to search all the node, each time we carry a color, for the next round, if not visited, give it a counter color; if visited, check if they have the same color. If two adjacent node have the same color, it is not bipartite.

Since the graph is not guarantee to be connected, we need to make sure our DFS runs on every part of the graph. If all parts of the graph can be partite, then the whole graph is bipartite.

Solution

​x
class Solution {
    // color : 1 & -1, not visited is 0
    bool recur(vector<vector<int>>& graph, int index, int color, vector<int>& visited) {
        if(visited[index]) {
            if(visited[index] == color) return false;
            return true;
        }
        
        int mycolor = -1 * color;
        visited[index] = mycolor;

        for(auto& i : graph[index]) {
            if(!recur(graph, i, mycolor, visited)) return false;
        }

        return true;
    }
public:
    bool isBipartite(vector<vector<int>>& graph) {
        
        vector<int> visited(graph.size(), 0);
        int starter = 0;
        for(;starter < graph.size(); ++starter) {
            if(visited[starter] == 0) {
                bool res = recur(graph, starter, 1, visited);
                if(res == false) return false;
            }
        }

        return true;
    }
};

Here I used the classic recursive function to implement DFS. The parameters are index: identify current node, color: the function caller's color for current node to reference, visited is an array to store the node:color mapping, and also as a mark to avoid circulation.

Worth to mention that in the main function, we iterate all nodes to make sure every part of the graph got DFS-ed.

Of course you can transform this DFS solution into a iterative approach with stack. That will probably have some performance increase.

What I learned

Reviewed the concept of bipartite and the coloring problem. The DFS is quite a powerful tool in graph problems.