·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=1182
参考博客：Azrael_Death的博客
以下引用自Azrael_Death大神：
逻辑推理的题有一部分和并查集有关，此题是种类并查集的经典例题。
首先我们把每个动物分成三个点，对于点i，点i表示第i个动物的种类，点i+n表示第i个动物的食物，点i+2n表示第i个动物的天敌。
这样一来，提供信息：x和y同类，相当于提供三条信息：
1.x、y在同一个集中
2.x+n、y+n在同一个集中
3.x+2n、y+2n在同一个集中
于是我们merge(x, y), merge(x+n, y+n), merge(x+2n, y+2n);
同理，提供信息：x吃y，相当于提供三条信息：
1.x、y+2n在同一个集中
2.x+n、y在同一个集中
3.x+2n、y+n在同一个集中
于是我们merge(x, y+2n), merge(x+n, y), merge(x+2n, y+n);
如果在接到信息x和y同类后，发现x和y+n同类或x和y+2n同类，则此信息与先前信息矛盾。因为对称性，我们不用再判断y是否和x+n或x+2n同类。同理可处理x吃y的情况。
然后贴上自己的代码。。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std;
int fa[50009*3];
int n,k;
int getfa(int x) {
if (fa[x]!=x) fa[x]=getfa(fa[x]);//return (fa[x]=getfa(fa[x]));不理解为什么用注释部分替换掉return语句后运行不出正确结果
return fa[x];
}
inline void merge(int x,int y) {
int ancx=getfa(x);
int ancy=getfa(y);
if (ancx!=ancy) fa[ancx]=ancy;
}
int main () {
int d,x,y,tot=0;
scanf("%d%d",&n,&k);
for (int i=1;i<=n*3;i++) fa[i]=i;
for (int i=0;i<k;i++) {
scanf("%d%d%d",&d,&x,&y);
if (x>n||y>n) {
tot++;
continue;
}
if (d==1) {
if (getfa(x)==getfa(y+n)||getfa(x)==getfa(y+2*n)
||x>n||y>n) tot++;
else {
merge(x,y);
merge(x+n,y+n);
merge(x+2*n,y+2*n);
}
}
else {
if (getfa(x)==getfa(y)||getfa(x)==getfa(y+n)
||x>n||y>n||x==y) tot++;
else {
merge(x,y+2*n);
merge(x+n,y);
merge(x+2*n,y+n);
}
}
}
printf("%d",tot);
}