神奇的UnionFind (1)

今天学习了神奇的并查集，UnionFind，试着做了几道之前用BFS/DFS的算法题，感觉超好用！

UnionFind的基础运用：

• 创建一个UnionFind
• 查找某元素所在group的大哥
• 连接两个元素
• 判断两个元素是否在同一个group中

那我们来看看题目吧！
Connecting Graph

Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning. You need to support the following method:

1. connect(a, b), add an edge to connect node a and node b.
   2.query(a, b), check if two nodes are connected

public class ConnectingGraph { 
    private int[] father = null;
    
    private int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }

    public ConnectingGraph(int n) {
        // initialize your data structure here.
        father = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            father[i] = i;
        }
    }

    public void connect(int a, int b) {
        // Write your code here
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }
        
    public boolean  query(int a, int b) {
        // Write your code here
        int rootA = find(a);
        int rootB = find(b);
        return (rootA == rootB);
    }
}