并查集

要使用并查集，题目必须满足某种传递性，且传递性必须是双向的，例如x=y,y=z,则能推出x=z，并且z=y，y=x，也能推出z=x。只要并查集中一个元素满足某种性质，那么集合中的所有元素都满足这种性质。

题目的两种问法：
1.简单：判断两个元素是否在同一个集合中。我们只需要维护一个并查集，判断两个元素的祖宗结点是否相同即可。
2.复杂：题目询问其他额外信息，如距离，集合元素个数等。这种情况我们所使用并查集要维护这个额外信息，一般可以将这个信息绑定在集合每个元素上，或者根节点上。
例如

• 根节点：集合中元素个数----整体性态 集合作为一个整体，合并一次集合就要修改一次

• 每个节点：和根节点的距离—局部性态 集合中每个元素是一个整体 合并一次集合要对新加入的元素修改

时间复杂度

C++ 代码

#include<iostream>
#include<string>
using namespace std;

const int N=210;
int n,m;
int p[N*N];

int get(int x,int y)
{
    return (x-1)*n+y-1;
}

int find(int x)
{
    if(x!=p[x])  p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    bool flag=false;
    for(int i=1;i<=n*n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        string op;
        cin>>x>>y>>op;

        int a=get(x,y);
        int b;
        if(op=="D") b=get(x+1,y);
        else b=get(x,y+1);

        int pa=find(a),pb=find(b);
        flag=false;

        if(pa==pb){
            cout<<i;flag=true;
            break;
        }
        p[pa]=pb;
    }
    if(flag==false) puts("draw");
    return 0;
}