第一反应就是和那个搞基的虫子的题很像（poj2492 http://www.cnblogs.com/wenruo/p/4658874.html），不过是把种类从2变成了3。
错在很白痴的地方，卡了好久……
代码：
/*********************************************
Problem: 1182 User: G_lory
Memory: 972K Time: 266MS
Language: G++ Result: Accepted
*********************************************/
#include <cstdio>
#include <cstring> using namespace std; const int N = 50005; int par[N];
int rank[N];
int rel[N]; // 0: same, 1: father eat son, 2: son eat father void init(int n)
{
for (int i = 0; i <= n; ++i) {
par[i] = i;
rank[i] = 0;
rel[i] = 0;
}
} int find(int x)
{
if (par[x] == x) return x;
return find(par[x]);
} // return 1 means root eat x, return 2 mean x eat root, return 0 mean same
int rel_root(int x)
{
int p, ans = 0;
for (p = x; p != par[p]; p = par[p]) {
ans = (ans + rel[p]) % 3;
}
return ans;
} void unite(int x, int y, int c)
{
int rootx = find(x);
int rooty = find(y);
if (rootx == rooty) return ;
int relx = rel_root(x);
int rely = rel_root(y);
if (rank[rootx] < rank[rooty]) {
par[rootx] = rooty;
rel[rootx] = ((rely - relx - c) % 3 + 3) % 3;
} else {
par[rooty] = rootx;
rel[rooty] = ((relx - rely + c) % 3 + 3) % 3;
}
if (rank[rootx] == rank[rooty]) ++rank[rootx];
} bool same(int x, int y)
{
return find(x) == find(y);
} int main()
{
int n, k;
int ch, x, y;
scanf("%d%d", &n, &k);
int ans = 0;
init(n);
for (int i = 0; i < k; ++i) {
scanf("%d%d%d", &ch, &x, &y);
if (x > n || x <= 0 || y > n || y <= 0) {
++ans;
continue;
}
if (ch == 1) {
if (same(x, y)) {
if (rel_root(x) != rel_root(y)) ++ans;
} else unite(x, y, 0);
} else {
if (same(x, y)) { // x eat y
if ( !((rel_root(x) == 0 && rel_root(y) == 1) ||
(rel_root(x) == 1 && rel_root(y) == 2) ||
(rel_root(x) == 2 && rel_root(y) == 0)) )
++ans;
} else unite(x, y, 1);
}
}
printf("%d\n", ans);
return 0;
}
并查集模板：
const int N = 300005; int par[N]; // father
int rank[N]; // height void init(int n)
{
for (int i = 0; i < n; ++i) {
par[i] = i;
rank[i] = 0;
}
} int find(int x)
{
if (par[x] == x) return x;
return par[x] = find(par[x]); // 压缩路径
} void unite(int x, int y)
{
x = find(x); y = find(y);
if (x == y) return ;
if (rank[x] < rank[y]) par[x] = y;
else par[y] = x;
if (rank[x] == rank[y]) ++rank[x];
} bool same(int x, int y)
{
return find(x) == find(y);
}