基本算法学习--并查集记录（有固定的解题模板）

(一）理论学习：

https://blog.****.net/dm_vincent/article/details/7655764

文中对并查集进行了理论说明和常用的建模方法，以及解决思路即：Quick-Find 算法, Quick-Union 算法

将所有的节点以整数表示，即对N个节点使用0到N-1的整数表示。而在处理输入的Pair之前，每个节点必然都是孤立的，即他们分属于不同的组，可以使用数组来表示这一层关系，数组的index是节点的整数表示，而相应的值就是该节点的组号了。该数组可以初始化为：

for(int i = 0; i < size; i++)
    id[i] = i; 

Quick-Find算法会造成牵一发而动全身；Quick-Union算法通过树将节点组织起来，涉及到极端情况下的复杂度，在进行合并过程中将树的高度考虑在内，即小的树合并到大的树上，避免出现线性表的极端情况，因此引入Weighted Quick-Union方法。下文解题主要用该方法进行。

文中列举的几种方法的复杂度：

（二）解题模板

（三）Leetcode刷题记录：

其中岛屿数量，同样可以套用算法模型，相同的UF,union,find,关键看connected的实现，记录属于哪个子类，二维数组用一维表示。

解决JAVA实现：

int [] sz;
int [] father;

public void initUF(int n) {
    sz = new int[n];
    father = new int[n];
    for (int i = 0; i < n; i++) {
        sz[i] = 1;
        father[i] = i;
    }
}

public int find(int p) {
    if (p != father[p]) {
        p = find(father[p]);
    }
    return p;
}

public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    if (sz[i] > sz[j]) {
        sz[i] += sz[j];
        father[i] = j;
    } else {
        sz[j] += sz[i];
        father[j] = i;
    }
}

public int numIslands(char[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int k = m * n;
    initUF(k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int t1 = i*m+j;
            int t2 = t1 + 1;
            int t3 = t1 + m;
            if (grid[i][j] == '1' && j+1<m && grid[i][j+1] == '1') {
                union(t1, t2);
            }
            if (grid[i][j] == '1' && i+1<n && grid[i+1][j] == '1') {
                union(t1, t3);
            }
        }
    }

    int num = 0;
    for (int i = 0; i < k; i++) {
        if (grid[i/m][i%m] == '1' && father[i] == i) {
            num++;
        }
    }
    return num;
}