并查集

概念
并查集是一种可以动态维护若干个不重叠的结合,并且支持合并与查询的数据结构.也就是擅长维护各种各样的具有传递性质的关系.

1、将两个集合合并
2、询问两个元素是否在一个集合当中

近乎O(1) 快速的支持两个操作

基本原理：每个集合用一颗树来表示

优化：路径压缩、按质合并(没什么用)

836.合并集合

#include<iostream>

using namespace std;

#define N 100010
int f[N];


int find(int x) //找到该节点的父节点
{
    if( f[x] != x)  f[x]=find(f[x]);
    return f[x];
}

int merge(int x,int y)
{
    f[find(x)] = find(y); //把x的父节点变为y的父节点
}
int main()
{
    int n,T;
    cin >> n >> T;
    for(int i = 1; i<=n;i++)
        f[i] = i; //每个点的父节点就是本身
    while(T--)
    {
        char c;
        int x,y;
        cin >> c >> x >> y;

        if( c == 'M')
            merge(x,y);
        else 
        {
            if( find(x) == find(y))
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
        }
    }

    return 0;
}

AcWing 837. 连通块中点的数量

#include<iostream>

using namespace std;

#define N 100010

int f[N];
int Size[N]; //开辟一个Size记录每一个集合的大小
int n,T;

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


void merge(int x,int y)
{

    Size[find(y)] += Size[find(x)]; //所以把x的节点数加到y上
    f[find(x)] = find(y); //再把x接到y的节点，合并
}


int main()
{

    cin >> n >> T;
    for(int i = 1 ;i <=n;i++)
    {
        f[i] = i;
        Size[i] = 1;
    }
    while(T--)
    {

        string c;
        int x,y;

        cin >> c;
        if(c == "Q2")
            cin >> x;
        else
            cin >> x >> y;
        //  cout << c << x << y << endl;
        if( c == "C")
        {
            if(find(x) == find(y)) //x,y属于同一个集合的时候，就不需要再合并了
                continue;
            merge(x,y);
        }
        else if(c == "Q1")
        {
            if( find(x) == find(y))
                puts("Yes");
            else
                puts("No");
        }
        else
        {
            cout << Size[find(x)] << endl;
        }
    }

}

求连通块的数量(裸题）

合根植物

#include<iostream>

using namespace std;

const int N = 1000000;
int f[N];

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

void merge(int x,int y)
{
    f[find(x)] = find(y);
}

int main()
{
    int n,m;
    cin >> n  >> m;
    for(int i = 1; i <=n*m;i++)
    {
        f[i] = i;
    }

    int T;
    cin >> T;
    while(T--)
    {
        int x,y;
        cin >> x >> y;
        merge(x,y);
    }

    int res = 0;
    for(int i =1;i<=n*m;i++)
    {
        if(f[i] == i)
            res++;
    }

    cout << res;
    return 0;
}

547.省份数量

class Solution {
public:
    int f[210]= {0};
    int find(int x)
    {
        if( f[x] != x )
            f[x] = find(f[x]);
        return f[x];
    }

    void merge(int x,int y)
    {
        f[find(x)] = find(y);
    }
    int findCircleNum(vector<vector<int>>& isConnected) {

        int n = isConnected.size();
        for(int i = 0; i <n;i++)
            f[i] = i;
        for(int i = 0; i<n;i++)
        {
            for(int j = i ;j<n;j++)
            {
                if(isConnected[i][j] == 1)
                    merge(i,j);
            }
        }
        int res = 0;
        for(int i = 0; i <n;i++)
            if(f[i] == i)
                res++;

        return res;

    }
};