這道題目并沒能做出來。
感覺最近睡眠比較少识藤，所以有些問題晚上根本想不清楚，尤其圖這種需要許多空間思考的次伶。
這道題目很重要痴昧，他介紹了一個(gè)基本知識(shí)。
如何判斷一個(gè)圖是否有環(huán)冠王。
當(dāng)然赶撰，這道題目還需要再多判斷一個(gè)問題：
如何判斷這個(gè)圖只有一個(gè)強(qiáng)連接部分 strong connected component

三種方法：
DFS, BFS, Union Find

我覺得 Union Find 最直接巧妙，也不用構(gòu)造圖柱彻，一個(gè)數(shù)組解決問題豪娜。

Union Find:
My code:

public class Solution {
    private int V = 0;
    private int[] id;
    private int[] sz;
    
    public boolean validTree(int n, int[][] edges) {
        this.V = n;
        id = new int[V];
        sz = new int[V];
        
        for (int i = 0; i < V; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        
        for (int i = 0; i < edges.length; i++) {
            int left = find(edges[i][0]);
            int right = find(edges[i][1]);
            if (left == right) {
                return false;
            }
            else {
                union(left, right);
            }
        }
        
        return edges.length == n - 1;
    }
    
    private int find(int index) {
        if (id[index] == index) {
            return index;
        }
        else {
            int ret = find(id[index]);
            id[index] = ret;
            return ret;
        }
    }
    
    private void union(int x, int y) {
        int id1 = find(x);
        int id2 = find(y);
        if (id1 == id2) {
            return;
        }
        else {
            if (sz[id1] > sz[id2]) {
                id[id2] = id1;
                sz[id1] += sz[id2];
            }
            else {
                id[id1] = id2;
                sz[id2] += sz[id1];
            }
        }
    }
}

reference:
https://discuss.leetcode.com/topic/21712/ac-java-union-find-solution

DFS:
My code:

public class Solution {
    private int V = 0;
    private List<List<Integer>> adj = new ArrayList<List<Integer>>();
    
    public boolean validTree(int n, int[][] edges) {
        this.V = n;
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            adj.get(v).add(u);
            adj.get(u).add(v);
        }
        
        boolean[] isVisited = new boolean[V];
        if (hasCycle(0, isVisited, -1)) {
            return false;
        }
        
        for (int i = 0; i < isVisited.length; i++) {
            if (!isVisited[i]) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean hasCycle(int u, boolean[] isVisited, int parent) {
        isVisited[u] = true;
        
        for (Integer temp : adj.get(u)) {
            if (isVisited[temp] && temp != parent) {
                return true;
            }
            else if (!isVisited[temp] && hasCycle(temp, isVisited, u)) {
                return true;
            }
        }
        
        return false;
    }
}

reference:
https://discuss.leetcode.com/topic/21714/ac-java-graph-dfs-solution-with-adjacency-list

BFS:
My code:

public class Solution {
    private int V = 0;
    private List<Set<Integer>> adj = new ArrayList<Set<Integer>>();
    
    public boolean validTree(int n, int[][] edges) {
        this.V = n;
        for (int i = 0; i < V; i++) {
            adj.add(new HashSet<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            adj.get(v).add(u);
            adj.get(u).add(v);
        }
        
        boolean[] isVisited = new boolean[V];
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(0);
        isVisited[0] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            n--;
            for (Integer v : adj.get(u)) {
                if (isVisited[v]) {
                    return false;
                }
                adj.get(v).remove(u);
                q.offer(v);
                isVisited[v] = true;
            }
        }
        
        return n == 0;
    }
}

reference:
https://discuss.leetcode.com/topic/57131/java-straightforward-bfs-solution

全部都自己寫了下。如果判斷環(huán)在graph里面應(yīng)該算是基本的算法哟楷，必須要掌握瘤载。

還有就是 topological sort

最重要的還是如果快速地構(gòu)建一個(gè)graph

Anyway, Good luck, Richardo! -- 09/10/2016