2017-07-28 17:27:41

writer：pprp

有两种优化方法：

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

题目：亲戚

---

代码如下：

#include 
     
      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"<