摘要：不在的話，表示不構(gòu)成環(huán)，我們應(yīng)該合并這兩個集合因為加上這條邊，兩個集合就被連起來了，合并成了一個集合注意如果想要復(fù)雜度為必須用路徑壓縮。并查集寫法參考注意方法用找的老大哥，合并的是的老大哥。

Given n nodes labeled from 0 to n - 1 and a list of directed edges (each edge is a pair of nodes), write a function to check whether the graph contains a cycle. if edges = [0, 1], [1, 2], [0, 2]], it means 0 -> 1, 1 ->2, 0 -> 2. edges[i is parent, edgesi is child.
For example:
Given n = 3 and edges = [[0, 1], [1, 2], [0, 2], return true. 
Given n = 3 and edges = [[0, 1], [1, 2], [2, 0], return false.

O( V + E ) 時間 O(V) 空間

什么是有向圖有環(huán)：只要從a可以到a，經(jīng)過的邊的個數(shù)大于等于1

做法：
維護(hù)三個點的集合：

白點集合，里面放還沒explore的點

灰點集合，里面放正在explore的點，當(dāng)前的灰點們表示一條正在explore的路徑，這個路徑上的每個點都是灰的

黑點集合，里面放已經(jīng)explore的點且這些點不構(gòu)成環(huán)

如果我將要的訪問的點是黑點，我是否需要訪問他？
答：不需要，一個點是黑的表示這個點的所有孩子(鄰居)都explore過了，且沒發(fā)現(xiàn)環(huán)，且這個點的所有孩子必定也全是黑的。

何時把一個點由灰變黑？
答：當(dāng)這個點的所有孩子都訪問完(都已變黑)了且沒有發(fā)現(xiàn)環(huán)

如果我將要訪問的點是個灰點，說明什么？
答：發(fā)現(xiàn)了環(huán)。假設(shè)explore到了cur點，cur點為灰色，此時所有其他的灰色點必定都是我的祖先，因為他們都是當(dāng)前explore的路徑上的點，cur在最戰(zhàn)線的最前方explore，如果cur點在explore的時候發(fā)現(xiàn)自己的的孩子(鄰居)有一個灰色，表示下面這個點即是我的祖先也是我的孩子，說明從cur可以走到cur自己，即出現(xiàn)了環(huán)。

無向圖和有向圖很不一樣，不是一回事

核心代碼：

public boolean hasCycleDirectedGraph(int n, int[][] edges) {//前指后
        HashSet black = new HashSet();
        HashSet white = new HashSet();
        HashSet gray = new HashSet();
        List> adjList = new ArrayList>();
        for (int i = 0; i < n; ++i) {
            white.add(new Integer(i));
            adjList.add(new ArrayList()); 
        }
            
        for (int[] edge: edges) {
            adjList.get(edge[0]).add(new Integer(edge[1]));
        }
        for (int i = 0; i < n; i++) {
            if (white.contains(i)) {
                if (hasCycle(i, white, gray, black, adjList))
                    return true;
            }
        }
        return false;
    }
    private boolean hasCycle(Integer vertex, HashSet white, HashSet gray, HashSet black, List> adjList) {
        white.remove(vertex);
        gray.add(vertex);  // current vertex is being visited
        for (Integer succ: adjList.get(vertex)) {  // successors of current vertex
            if (white.contains(succ)) {
                if (hasCycle(succ, white, gray, black, adjList))
                    return true;
            }
            else if (gray.contains(succ)) {
                return true;
            }
            else if (black.contains(succ)) {
                continue;
            }        
        }
        gray.remove(vertex);
        black.add(vertex);
        return false;
    }

測試代碼：

public class Solution {
    public static void main(String[] args) {
        Solution so = new Solution();
        int[][] edges = {{0, 1}, {1, 2}, {2, 0}};
        boolean result = so.hasCycleDirectedGraph(3, edges);
        System.out.println(result);
    }
}

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether the graph contains a cycle.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return false.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return true.

O( V + E ) 時間 O(V) 空間

什么是無向圖有環(huán)：只要從a可以到a，路徑中每個邊只用一次

數(shù)據(jù)結(jié)構(gòu)：
并查集：
規(guī)定集合(即一個連通分量)應(yīng)該滿足的property:里面的任意兩點有且只有一條路徑可達(dá)。
最開始的時候n個點有n個連通分量，即n個集合。

做法：

想象一開始這個圖只有頂點，沒有邊，我們來一條一條的添加邊。
每遇到一條邊，判斷這邊的兩個端點是否在同一個集合里？

在的話，表示有環(huán)：因為兩個點在一個集合里就表示這兩個點已經(jīng)有一條路徑了，現(xiàn)在再加一條路徑，必然構(gòu)成環(huán)。

不在的話，表示不構(gòu)成環(huán)，我們應(yīng)該合并這兩個集合：因為加上這條邊，兩個集合就被連起來了，合并成了一個集合

如果想要復(fù)雜度為O(V+E),必須用路徑壓縮。
并查集寫法參考
注意union(p,q)方法：用find()找p,q的老大哥，合并的是p,q的老大哥。

UnionFind Utility(非常intuitive，應(yīng)該練習(xí)在5分鐘內(nèi)寫完):

class UnionFind {
    private int[] father;
    private int count;
    public UnionFind(int n) {
        father = new int[n];
        count = n;
        for (int i = 0; i < n; i++){
            father[i] = i;
        }
    }
    public int count() {
        return this.count;
    }
    public int find(int p) {
        int root = father[p];
        while (root != father[root])
            root = father[root];
        //as long as we get here, root is the final dad
        while (p != root) {
            int tmp = father[p];
            father[p] = root;
            p = tmp;
        }
        return root;
    }
    public void union(int p, int q) {
        int fatherP = find(p);
        int fatherQ = find(q);
        if (fatherP != fatherQ) {
            father[fatherP] = fatherQ;
            count--;
        }
    }
}

主程序

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges){
            int p = edge[0];
            int q = edge[1];
            if (uf.find(p) == uf.find(q))
                return false;
            else
                uf.union(p,q);
        }
        return uf.count() == 1;
    }
}

O( V + E ) 時間 O(V) 空間

無向圖找環(huán)和有向圖找環(huán)本質(zhì)上完全不同。
有向圖找環(huán)需要三種顏色。
無向圖找環(huán)只需要兩種顏色，就是訪問過的和沒訪問的。

dfs過程中如果碰到訪問過的節(jié)點(當(dāng)然這個節(jié)點不能是來時的節(jié)點)，就是有環(huán)。

Integer的比較問題

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        HashSet visited = new HashSet();
        List> adjList = new ArrayList>();
        for (int i=0; i()); 
        for (int[] edge: edges) {
            adjList.get(edge[0]).add(edge[1]);
            adjList.get(edge[1]).add(edge[0]);
        }
        if (hasCycle(-1, 0, visited, adjList))  // has cycle?
            return false;   
        if (visited.size() != n) // is all connected?
            return false;   
        return true;
    }

    private boolean hasCycle(Integer pred, Integer vertex, HashSet visited, List> adjList) {
        visited.add(vertex);  // current vertex is being visited
        for (Integer succ: adjList.get(vertex)) {  // successors of current vertex
            if (!succ.equals(pred)) {  // exclude current vertex"s predecessor
                if (visited.contains(succ)) { 
                    return true; // back edge/loop detected!
                }  
                else  {
                    if (hasCycle(vertex, succ, visited, adjList)) { 
                        return true; 
                    }
                }
            }
        }
        return false;
    }
}