poj-1182 类别并查集
poj-1182 种类并查集
转：用0 1 2 分别表示A B C的关系。
0吃1,1吃2,2吃0.
注意这个编号都是以根结点为参照的，不是绝对的。
开一个val数组，一开始这个数组为0，所有的点都是独立的，不是相连的，没有关系。
慢慢加入点之后，把有关系的合并在一起，并且编号的相对大小确定一个集合中的关系。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
int n, k, d, x, y;
int fa[50010];
int rankk[50010];
int ans;
int findd(int x)
{
if (fa[x] == -1)
return x;
int tmp = findd(fa[x]);
rankk[x] += rankk[fa[x]];
rankk[x] %= 3;
return fa[x] = tmp;
}
int main()
{
scanf("%d %d",&n,&k);
{
memset(fa,-1,sizeof(fa));
memset(rankk,0,sizeof(rankk));
ans = 0;
while (k--)
{
scanf("%d %d %d", &d, &x, &y);
if (x > n || y > n)
{
ans++;
continue;
}
int fx = findd(x);
int fy = findd(y);
if (fx == fy)
{
if (d == 1 && rankk[x] != rankk[y])
ans++;
if (d == 2 && (rankk[x] + 1) % 3 != rankk[y])
ans++;
}
else
{
if (d == 1)
{
fa[fy] = fx;
rankk[fy] = rankk[x] - rankk[y];
rankk[fy] = (rankk[fy] + 3) % 3;
}
else
{
fa[fy] = fx;
rankk[fy] = rankk[x] - rankk[y] + 1;
rankk[fy] = (rankk[fy] + 3) % 3;
}
}
}
printf("%d\n",ans);
}
return 0;
}