Leetcode 261. 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.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

是否成环问题

这道题可以联系 Leetcode 207. course schedule 一同分析，当我们把题意扯开，他们的核心都是判断一个图是有环图，还是无环图。
而这两个问题的核心区别在于向的问题，261 Graph Valid Tree 是判断无向图是否有环，而207 course schedule 是判断有向图是否有环。
我把这个类型的规律总结如下，
如果题目给出向前依赖关系，即给定a依赖于b,c,d,e, 则DFS更适合；
如果题目给出向后依赖关系，即给定a支持b,c,d,e,则BFS更适合；
如果题目给出无向图，则BFS与DFS大致等价

BFS 实现

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n==0||n==1) return true;
        if (edges==null||edges.length==0) return false;
        List<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[n];
        for (int[] edge:edges){
            if (graph[edge[0]]==null) graph[edge[0]] = new ArrayList<>();
            if (graph[edge[1]]==null) graph[edge[1]] = new ArrayList<>();
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        int root = edges[0][0];
        List<Integer> queue = new ArrayList<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int number = queue.size();
            for (int i=0;i<number;i++){
                int node = queue.remove(0);
                if (visited.contains(node)) return false;
                visited.add(node);
                queue.addAll(graph[node]);
                for (int dest:graph[node]){
                    graph[dest].remove((Integer)node);
                }
            }
        }
        return visited.size()==n;
    }
}

DFS实现

class Solution {

    private HashSet<Integer> visited;
    private int n;
    private int[][] graph;

    private boolean dfs(int node){
        for (int dest=0;dest<n;dest++){
            if (graph[node][dest] == 0) continue;
            if (visited.contains(dest)) return false;
            visited.add(dest);
            graph[node][dest] = 0;
            graph[dest][node] = 0;
            if (!dfs(dest)) return false;
        }
        return true;
    }

    public boolean validTree(int n, int[][] edges) {

        if (n==0||n==1) return true;
        if (edges==null || edges.length==0) return false;
        this.n = n;
        graph = new int[n][n];
        visited = new HashSet<>();
        for (int[] edge:edges){
            graph[edge[0]][edge[1]] = 1;
            graph[edge[1]][edge[0]] = 1;
        }
        visited.add(edges[0][0]);
        int root = edges[0][0];
        return dfs(root) && visited.size()==n;
    }
}