261. Graph Valid Tree

Published on April 22, 2023

Question

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.

Algorithm

We are asking to find if the given graph is a tree. A tree is a connected acyclic graph.

So we could know our union find is to do this. To check if there is a cycle. When we do the union operation, we try to put vertexes of an edge into same set, then we find that they are already in a set. This indicates that there is a cycle.

And we need to check the graph is connected. First I traverse all the nodes in a double loop to see if they are connected. However, we only need to check if the edge number is node number minus one.

Code

class Solution {
    int[] parents;
    int[] size;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        parents = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            size[i] = 1;
        }
        
        for (int[] edge : edges) {
            if (union(edge[0], edge[1], n) == false) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean union(int x, int y, int n) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) {
            return false;
        }
        if (size[xRoot] > size[yRoot]) {
            parents[yRoot] = xRoot;
            size[xRoot] += size[yRoot];
        } else {
            parents[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        }
        return true;
    }
    
    private int find(int x) {
        if (x != parents[x]) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }
}