Graph Valid Tree

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 these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.” Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Tips:

UF方法：复杂度 O(n)

• 与Number of connected components in an Undirected Graph 非常类似，只是输出结果是boolean。
• 仍旧计算无向联通块的个数，如果最后结果为1则返回true，否则返回false。
• 不同的是在对edge做UF操作的时候需要加一个判断来判断是否构成cycle，如果构成则不是树。

    if (n == 1) {
        return true;
    }
  

DFS和BFS方法简单贴了一下。

Code:

UF:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 1) {
            return true;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, i);
        }
        for (int[] edge : edges) {
            int fa_x = find(edge[0], map);
            int fa_y = find(edge[1], map);
            if (fa_x == fa_y) {
                return false;
            }
            if (fa_x != fa_y) {
                map.put(fa_x, fa_y);
                n--;
            }
        }
        if (n == 1) {
            return true;
        }
        return false;
    }
    private int find(int x, HashMap<Integer, Integer> map) {
        int father = map.get(x);
        while (father != map.get(father)) {
            father = map.get(father);
        }
        //compressed:
        while (x != map.get(x)) {
            temp = map.get(x);
            map.put(x, father);
            x = temp;
        }
        //end
        return father;
    }
}

DFS:

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize adjacency list
        List<List<Integer>> adjList = new ArrayList<List<Integer>>(n);

        // initialize vertices
        for (int i = 0; i < n; i++)
            adjList.add(i, new ArrayList<Integer>());

        // add edges    
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            adjList.get(u).add(v);
            adjList.get(v).add(u);
        }

        boolean[] visited = new boolean[n];

        // make sure there's no cycle
        if (hasCycle(adjList, 0, visited, -1))
            return false;

        // make sure all vertices are connected
        for (int i = 0; i < n; i++) {
            if (!visited[i]) 
                return false;
        }

        return true;
    }

    // check if an undirected graph has cycle started from vertex u
    boolean hasCycle(List<List<Integer>> adjList, int u, boolean[] visited, int parent) {
        visited[u] = true;

        for (int i = 0; i < adjList.get(u).size(); i++) {
            int v = adjList.get(u).get(i);

            if ((visited[v] && parent != v) || (!visited[v] && hasCycle(adjList, v, visited, u)))
                return true;
        }

        return false;
    }
}

BFS:

private boolean valid(int n, int[][] edges)
{
    // build the graph using adjacent list
    List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
    for(int i = 0; i < n; i++)
        graph.add(new HashSet<Integer>());
    for(int[] edge : edges)
    {
        graph.get(edge[0]).add(edge[1]);
        graph.get(edge[1]).add(edge[0]);
    }

    // no cycle
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new ArrayDeque<Integer>();
    queue.add(0);
    while(!queue.isEmpty())
    {
        int node = queue.poll();
        if(visited[node])
            return false;
        visited[node] = true;
        for(int neighbor : graph.get(node))
        {
            queue.offer(neighbor);
            graph.get(neighbor).remove((Integer)node);
        }
    }

    // fully connected
    for(boolean result : visited)
    {
        if(!result)
            return false;
    }

    return true;
}