poj 2492

带权并查集

 带权并查集即是结点存有权值信息的并查集；当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系；带权并查集每个元素的权通常描述其与并查集中祖先的关系，这种关系如何合并，路径压缩时就如何压缩；带权并查集可以推算集合内点的关系，而一般并查集只能判断属于某个集合。

A Bug's Life || 带权并查集

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2111;

int f[maxn],w[maxn];//每个结点的父亲及树高

//初始化n个元素
void init(int n)
{
    for(int i = 1; i <= n; ++i)  f[i] = i, w[i] = 0;
}

//查询树的根
int find(int x)
{
    if(f[x] == x) return x;
    int tmp = f[x];
    f[x] = find(f[x]);
    w[x] = (w[tmp] + w[x]) % 2;
    return f[x];
}

//合并x和y所属的集合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    f[x] = y;
}

int main()
{
    int n, m, x, y, t, xx, yy;
    scanf("%d", &t);
    for(int q = 1; q <= t; ++q)
    {
        printf("Scenario #%d:
", q);
        scanf("%d %d", &n, &m);
        init(n);
        bool flag = 0;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d", &x, &y);
            //printf("%c %d %d
", c, x, y);
            xx = find(x),  yy = find(y);
            if(xx == yy)
            {
                if(w[x] == w[y])
                flag = 1;
            }
            else
            {
                f[xx] = yy;
                w[xx] = (w[y] - w[x] + 3) % 2;
            }
        }
        if(flag) printf("Suspicious bugs found!
");
        else printf("No suspicious bugs found!
");
        if(q != t) printf("
");
    }
}