题目描述
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。
A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。
每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N和K句话，输出假话的总数。
输入格式
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤500001≤N≤50000,
0≤K≤1000000≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3题解：这题我们有两种解法，一种是带权并查集，还一种是扩展域并查集。
先来讲带权并查集的做法，我们定义一个d数组，d[x]表示x到fa[x]的权值。三类动物的关系为...->A->B->C->A...，我们可以设每个->传递的值为1，,同类的权值为0，吃为1，被吃为2。
当每给出一句话的时候我们先判断X与Y是否存在关系（如果前面给出了X与Y的关系会用并查集把它们并在一起，所以这一步判断它们的fa是否相同即可），如果有关系的话我们判断它们的关系是否与这句话给出的相符。 由上述关系我们可知A -> B 为1表示A吃B，B->C为1表示B吃C，A->B->C即A->C为2表示A被C吃，A->B->C->A为3即A->A是3，3%3=0，所以我们在可以通过%3来判断。没关系的话，我们就将X的祖先与Y的祖先并起来并更新X的祖先与Y的祖先间的权值，d[X的祖先] = d[y]+z-d[x]，因为X的祖先是与y有关系，然后加上现在的关系所以d[y]+z，又因为更新祖先时，会将d再加一遍所以-d[x]。
用扩展域并查集解需要把fa范围扩大到3倍。我们可以把1~n看做A类动物，n+1到2*n看做B类动物，2*n+1~3*n看做C类动物。
因为我们并不能确定它们具体是哪一类，只能确定相对关系，当X、Y是同类的时候，我们在三类中都把X、Y合并：join(x,y); join(x+n,y+n); join(x+2*n,y+2*n);当X吃Y的时候我们可以把X看做A类Y看做B类join(x,y+n);、把X看做B类Y看做C类join(x+n,y+2*n);、把X看做C类Y看做A类join(x+2*n,y)。
同样，在合并之前我们需要判断是否与前面给出的不相符。如果这句话是说X、Y是同类，那么我们需要判断X是否吃Y或者Y是否吃X，因为我们前面合并的时候三类都合并了，所以我们只要假设X是A类Y是B类或者X是B类Y是A类时他们是否被并在一起即可：if (Find(x) == Find(y+n)||Find(y) == Find(x+n))。同理，如果说X吃Y，那么我们需要判断X、Y是否为同类或者Y是否吃X，也只要各选一种情况来判断：if (Find(x) == Find(y)（同类）||Find(y) == Find(x+n)（被吃）)。
我们要注意还有两点：当前的话中X或Y比N大，就是假话；当前的话表示X吃X，就是假话。
代码：
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int N = 5e4 + ;
const double eps = 1e-;
int fa[N],d[N];
int Find(int x) {
if (x == fa[x]) return x;
int r = Find(fa[x]);
d[x] += d[fa[x]];
return fa[x] = r;
}
int main() {
int n,m,k,x,y,ans = ;
scanf("%d%d",&n,&m);
for (int i = ; i < n; i++) fa[i] = i;
for (int i = ; i < m; i++) {
scanf("%d%d%d",&k,&x,&y);
if (x<||y<||x>n||y>n) ans++;
else if (k == && x == y) ans++;
else {
int z = (k==?:);
int xx = Find(x),yy = Find(y);
if ( xx == yy) {
if (((d[x] - d[y])%+)% != z) ans++;
}else {
fa[xx] = yy;
d[xx] = d[y] + z - d[x];
}
}
}
printf("%d\n",ans);
return ;
}
带权并查集
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int N = 2e5 + ;
const double eps = 1e-;
int fa[N];
int Find(int x) {
return x==fa[x]?x:fa[x] = Find(fa[x]);
}
void join(int x,int y) {
int xx = Find(x),yy = Find(y);
fa[xx] = yy;
}
int main() {
int n,m,d,x,y,ans = ;
scanf("%d%d",&n,&m);
for (int i = ; i < N; i++) fa[i] = i;
for (int i = ; i < m; i++) {
scanf("%d%d%d",&d,&x,&y);
if (x<||y<||x>n||y>n) ans++;
else if (d == ) {
if (Find(x) == Find(y+n)||Find(y) == Find(x+n)) ans++;
else {
join(x,y);
join(x+n,y+n);
join(x+*n,y+*n);
}
}else if (d == ) {
if (Find(x) == Find(y)||Find(y) == Find(x+n)) ans++;
else {
join(x,y+n);
join(x+n,y+*n);
join(x+*n,y);
}
}
}
printf("%d\n",ans);
return ;
}
扩展域并查集