并查集

初始化：

for(int i = 1;i <= n; ++i)
 f[i] = i;

路径压缩：

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

合并：

f[find(x)] = find(y);

NOIP2010关押罪犯：构造虚点
假设x号罪犯与y号罪犯是仇人，x+n号罪犯与y+n号罪犯是仇人，那么可以推出：如果x与y在同一个监狱了，则x+n号犯人与y+n号也在同一个监狱里，一定会发生冲突

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
    int x,y,z;
}a[100010];

int n,m,f[50000];

bool cmp(node k,node p)
{
    return k.z > p.z;
}

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

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n * 2; ++i) f[i] = i;
    for(int i = 0;i < m; ++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a , a + m , cmp);
    for(int i = 0;i < m; ++i)
    {
        if(find(a[i].x) == find(a[i].y))
        {
            printf("%d\n",a[i].z);
            return 0;
        }
        f[find(a[i].x)] = find(a[i].y + n);
        f[find(a[i].y)] = find(a[i].x + n);
    }
    printf("0\n");
    return 0;
}

NOI2002银河英雄传说
在应用并查集的通识维护每列的总数以及每列中战舰到队列最前面的距离

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int f[30010],d[30010],last[30010];
int n,x,y;
char c;

int find(int x)
{
    if(f[x] == x) return x;
    int p = f[x];
    f[x] = find(f[x]);
    d[x] += d[p];
    return f[x];
}

int main()
{
    for(int i = 1;i <= 30000; ++i)
    {
        d[i] = 0;
        f[i] = i;
        last[i] = 1;
    }
    scanf("%d",&n);
    for(int i = 0;i < n; ++i)
    {
        cin>>c;
        scanf("%d%d",&x,&y);
        //cout<<c<<endl;
        if(c == 'M')
        {
            x = find(x);
            y = find(y);
            f[x] = y;
            d[x] += last[y];
            last[y] += last[x];
        }
        else
        {
            if(find(x) != find(y)) printf("-1\n");
            else
            {
                printf("%d\n",abs(d[x] - d[y]) - 1);
               // printf("%d %d",d[x],d[y]);
            }
        }
    }
    return 0;
}