classic union find


  • 0
    M

    public class Solution {
    int[] nums;
    public boolean validTree(int n, int[][] edges) {
    this.nums = new int[n];
    for (int i = 0; i < n; i++) {
    nums[i] = i;
    }
    for (int[] edge : edges) {
    int n1 = find(edge[0]);
    int n2 = find(edge[1]);
    if (n1 == n2) {
    return false;
    } else {
    nums[n1] = n2;
    }
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
    if (i == nums[i]) {
    count++;
    }
    }
    return count == 1;
    }

    public int find (int num) {
        if (nums[num] == num) {
            return num;
        }
        nums[num] = find(nums[num]);
        return nums[num];
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.