算法课6-并查集Union Find

为了提高查找速度，三种方法：

Link by size
Link by rank(height)
Path Compression

并查集的典型应用：
Percolation
总时间限制: 1000ms 内存限制: 32768kB
描述
定义一个N行N列的矩阵，矩阵中的每个元素是个方格，每个方格有两种可能的状态：开通的或关闭的。初始时，所有方格都是关闭的。输入数据的每一步会指定矩阵中某个原来关闭的方格变成开通的。要求编写程序判断当前是否存在从矩阵中最上面一行的任何一个开着的方格走到最下面一行的任何一个开着的方格的路径。如果存在的话，输出当前的步数。比如走到第14步时，矩阵变成上下通透的，那么就输出14。注意：输入数据中只会把矩阵中的一部分方格打开。如果所有步骤都执行完了，矩阵仍然不是上下通透的，那么输出-1。显然，矩阵变成上下通透的一个必要条件是：最上面一行和最下面一行都至少要有一个方格是打开的。

在矩阵中行走时，只能横着走或竖着走，不能斜着走，也不能走出矩阵的边界。

输入
输入的第一行是一个自然数T(1≤T≤10)，代表测试数据的组数。每组测试数据的第一行有两个自然数N和M，其中N（1≤N≤1,000）代表方阵的维度，M（1≤M≤N*N）代表本组测试中打开的方格数目。随后的M行中每行有两个自然数，分别代表所打开的方格的行、列下标。注意：本题中矩阵的下标从1开始，即所有下标的取值都是[1, N]区间中的正整数。
输出
每组测试数据输出一个自然数K，表示打开第K个方格后，矩阵变成上下通透的。如果M个方格都打开后，矩阵仍然不是上下通透的，那么输出-1。
样例输入

1
4 10
2 2
3 1
4 2
4 4
1 2
2 3
2 1
3 2
3 4
3 1

样例输出

8

#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<functional>
#include<vector>
using namespace std;
int t;
int n,m;
int id[1000005];

int find(int index){
//    while (index != id[index])
//    {index = id[index];}
    if(id[index]!=index){
        return id[index]=find(id[index]); //使用了路径压缩
    }
    return index;
}
void union_tree(int index1,int index2){
    int pRoot=find(index1);
    int qRoot=find(index2);
    if(pRoot==qRoot) return;
    id[pRoot]=qRoot;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int j=0;j<=n*n+1;j++){
            id[j]=-1;
        }
        bool res=false;
        for(int i=1;i<=m;i++)
        {
            int index1, index2;
            cin >> index1 >> index2;
            if(!res) {

                int loc = (index1 - 1) * n + index2;
                id[loc] = loc;
                //第一行
                if (loc <= n && loc > 0) {
                    id[0] = 0;
                    union_tree(loc, 0);
                }
                //最后一行
                if (loc > n * (n - 1) && loc <= n * n) {
                    id[n * n + 1] = n * n + 1;
                    union_tree(loc, n * n + 1);
                }
                //左边
                if (loc % n > 1 && id[loc - 1] != -1) {
                    union_tree(loc, loc - 1);
                }
                //上面
                if (loc / n > 0 && id[loc - n] != -1) {
                    union_tree(loc, loc - n);
                }
                //下面
                if (loc + n <= n * n && id[loc + n] != -1) {
                    union_tree(loc, loc + n);
                }
                //右边
                if (loc % n != 0 && id[loc + 1] != -1) {
                    union_tree(loc, loc + 1);
                }
                if(id[0] != -1 && id[n * n + 1] != -1&&find(0)==find(n*n+1)){
                    cout<<i<<endl;
                    res=true;
                }
            }

        }
        if(!res) cout<<-1<<endl;
    }
    return 0;
}

Kruskal’s algorithm 算法课5

LeetCode
Number of Islands
Longest Consective Sequence这道题的连续是说+1 或者-1 紧的连续
Surrounded regions 使用一个dummy node 标记

算法课6-并查集Union Find

相关推荐