General

261 Valid Graph

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.

• 節點跟邊個數的關係

• 連邊的時候查詢是否會形成環

class UF{
    private int[] parent;
    private int[] size;
    private int count;

    public UF(int n){
        parent = new int[n];
        size = new int[n];
        count = n;

        for(int i=0; i<n; i++) parent[i]=i;
        for(int i=0; i<n; i++) size[i]=1;
    }

    private int find(int x){
        if(parent[x] != x) parent[x]=find(parent[x]);
        return parent[x];
    }

    private void union(int x, int y){
        int root_x = find(x);
        int root_y = find(y);
        if(root_x == root_y) return;

        if(size[root_x] > size[root_y]){
            parent[root_y] = root_x;
            size[root_x]+=size[root_y];
        }else{
            parent[root_x] = root_y;
            size[root_y]+=size[root_x];
        }
        count--;
    }
}
public boolean validTree(int n, int[][] edges) {
    // 節點跟邊的關係
    if(n-1 != edges.length) return false;
    UF uf = new UF(n);

    // 是否形成環
    for(int[] edge: edges){
        if(uf.find(edge[0]) == uf.find(edge[1])) return false;
        uf.union(edge[0], edge[1]);
    }
    return true;
}

1396t. Set Union

There is a list composed by sets. If two sets have the same elements, merge them. In the end, there are several sets left.

• Init a int[] with -1 to represent the parentID of num

• Union the groups if the num has initialized

class UF{
    int[] parent;
    int[] size;
    int count;

    public UF(int n){
        parent = new int[n];
        size = new int[n];
        count = n;

        for(int i=0; i<n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x){
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y){
        int root_x = find(x);
        int root_y = find(y);

        if(root_x == root_y) return;
        if(size[root_x] < size[root_y]){
            parent[root_x] = root_y;
            size[root_y] += size[root_x];
        }else{
            parent[root_y] = root_x;
            size[root_x] += size[root_y];
        }
        count--;
    }
}

public class Solution {
    public int setUnion(int[][] sets) {
        UF uf = new UF(sets.length);

        int[] groupOfnum = new int[100001];

        // mark as -1 as don't have group yet
        for(int i=0; i<groupOfnum.length; i++){
            groupOfnum[i] = -1;
        }

        for(int i=0; i<sets.length; i++){
            for(int j=0; j<sets[i].length; j++){
                if(groupOfnum[sets[i][j]] == -1){
                    groupOfnum[sets[i][j]] = i;
                }else{
                    uf.union(i, uf.find(groupOfnum[sets[i][j]]));
                    groupOfnum[sets[i][j]] = i;
                }
            }
        }
        return uf.count;
    }
}