# 0785. Is Graph Bipartite?
###### tags: `Leetcode` `Medium` `FaceBook` `DFS` `Union Find` `DFS-color`
Link: https://leetcode.com/problems/is-graph-bipartite/
## 思路
这道题的意思其实就是看每条边的两个点能不能分别在两个不同set里面，如果能就返回true，否则返回false
### DFS $O(N+E)$ $O(N)$ $N$是node的个数 $E$是edge的个数
拿到一条边之后将两个点标记不同的颜色(-1,1), DFS做下去，如果发现两个点的颜色一样，则返回false，可以全部标完则标记true
时间复杂度分析：因为访问了每个node各一次，每条edge各一次
### Union Find
对于每一点来说 先判断它和它的neighbor在不在同一个group里面 在的话return false
接下来把所有它的neighbor放在一个group里面
## Code
### DFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        for(int i = 0;i < color.length;i++){
            if(color[i] == 0){
                color[i] = 1;
                Stack<Integer> stack = new Stack<>();
                stack.push(i);
                while(!stack.isEmpty()){
                    int curr = stack.pop();
                    int[] next = graph[curr];
                    for(int j = 0;j < next.length;j++){
                        if(color[next[j]]==0){
                            color[next[j]]=-color[curr];
                            stack.add(next[j]);
                        }
                        else if(color[next[j]]==color[curr]) return false;
                    }
                }
            }
        }
        return true;
    }
}

### Union Find

class Solution {
    int[] fa;
    public boolean isBipartite(int[][] graph) {
        fa = new int[graph.length];
        for(int i=0; i<graph.length; i++){
            fa[i] = i;
        }
        for(int i=0; i<graph.length; i++){
            int[] nexts = graph[i];
            for(int next:nexts){
                if(sameGroup(i, next)) return false;
                combine(next, graph[i][0]);
            }
        }
        return true;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private boolean sameGroup(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return true;
        return false;
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[b]=a;
    }
}