并查集

2017-07-28 17:27:41

writer：pprp

有两种优化方法：

1. 路径压缩，在初始化某节点至根节点的路径后，将这条路径上所有的节点都设为根节点，这样将复杂度降为最低；
2. 启发式合并，在合并两个结合的时候，将节点少的树合并到节点多的树上，也可以将高度小的树合并到高度大的树上；

题目：亲戚

---

代码如下：

#include <iostream>

using namespace std;

int N,M,Q;
int parent[1000];

int Find(int x)       //判断x所属集合
{
    int root = x;
    while(parent[root]>=0)    //找到根节点
        root = parent[root];
    while(root!=x)            //压缩路径,将该点直接
    {
        int tmp = parent[x];
        parent[x]= root;
        x = tmp;
    }
    return root;
}

void Merge(int a,int b)     //较小的树成为较大的树的子树
{
    int pa = Find(a);
    int pb = Find(b);
    if(pb < pa)
        swap(pb,pa);
    if(pa!=pb)
        parent[pb] = pa;
}

int main()
{
    int i,a,b;
    cin >> N >> M >> Q;

    for(i=1; i<=N; i++)
    {
        parent[i] = -1;
    }
    for(i=1; i<=M; i++)
    {
        cin >> a >> b;
        if(Find(a)!=Find(b))
            Merge(a,b);
    }
    for(i=1; i<=Q; i++)
    {
        cin >> a >> b;
        if(Find(a)==Find(b))
            cout <<"Yes"<<endl;
        else
            cout <<"No"<<endl;
    }

    return 0;
}