261. Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• There are no self-loops or repeated edges.

Solution:

class Solution {
    public boolean validTree(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i = 0; i < n; i++){
            graph.put(i, new ArrayList<>());
        }
        // 0: 1
        // 1:
        // 2: 3
        // 3:

        for (int[] e : edges){
            int from = e[0];
            int to = e[1];
            graph.get(from).add(to);
            graph.get(to).add(from);
        }// 

        // 0: 2
        // 1: 2
        // 2: 


        Set<Integer> visited = new HashSet<>();
        boolean isFindCycle = dfs(0, -1, graph, visited);
        if (isFindCycle == true){
            return false;
        }

        if (visited.size() != n){
            return false;
        }

        return true;

    }

    private boolean dfs(int i, int parent, Map<Integer, List<Integer>> graph, Set<Integer> visited){
        if (visited.contains(i)){
            return true;
        }
        // 1, graph, visited

        visited.add(i);// 0, 1
        // 1

        // 0
        // 2

        List<Integer> next = graph.get(i); // 1
        for (int nei : next){
            if (nei == parent){
                continue;
            }
            if (dfs(nei, i, graph, visited) == true){
                // 1, graph, 0
                return true;
            }
        }

        return false;
    }
}

DFS

class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<List<Integer>>();

        for (int i = 0; i < n; i++){
            adj.add(new ArrayList<Integer>());
        }
        // [1,2,3] [0,4] [0] [0] [1] 

        for (int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        boolean[] visited = new boolean[n];
        //  0 1 2 3 4 
        //  T T T T T
        int index = 0;
        int parent = -1;
        if (dfs(index, visited, adj, parent)){ // wether has cycle
            return false;
        }

        for (int i = 0; i < n; i++){
            if (visited[i] == false){
                return false;
            }

        }

        return true;

    }


    private boolean dfs(int node, boolean[] visited, List<List<Integer>> adj, int parent){
        if (visited[node] == true){
            return true;
        }

        visited[node] = true;

        for (int next : adj.get(node)){
            if (parent != next && dfs(next, visited, adj, node)){
                return true;
            }
        }

        return false;
    }
}

// TC: O(n)
// SC: O(n)

UnionFind

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

        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges){
            if (uf.connected(edge[0], edge[1])){
                return false;
            }else{
                uf.union(edge[0], edge[1]);
            }
        }

        for (int i = 0; i < n - 1; i++){
            if (uf.connected(i, i + 1) == false){
                return false;
            }
        }

        return true;
    }
}

class UnionFind{
    int[] root;
    // int[] size;

    public UnionFind(int n){
        root = new int[n];

        for (int node = 0; node < n; node++){
            root[node] = node;
        }
    }

    public int find(int x){
        while(x != root[x]){ 
            x = root[x];
        }
        return x;
    }

    public void union(int x, int y){
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY){
            root[rootY] = rootX;
        }
    }

    public boolean connected(int x, int y){
        return find(x) == find(y);
    }


}
// TC: O(V * E)
// SC: O(V)