数据结构：并查集-拆点

POJ1182

有三种动物，告诉A类吃B类，B类吃C类，C类吃A类

告诉你X和Y是同类或者是X吃Y，然后问给出的信息有几条和前面相违背

在这里我们用三个并查集来维护，把每一种动物拆成三类（因为我不知道它到底属于哪一个类别）

以下图片转自：https://blog.csdn.net/backforward/article/details/51892505

如果告诉你X和Y是同类，那么就这样归并

将A的每个节点与B的下一个节点相连

然后，如果告诉你X和Y是捕食关系，那样这么归并

如此处理之后

给出两个动物便可通过三个节点的相连情况得出二者的关系，从而判断真假

如果没毛病，就归并，有毛病就是矛盾的，跳过这句话

 1 #include<cstdio>
 2 const int maxn=50005;
 3 int n,m,ans;
 4 int fa[3*maxn];
 5 int find(int x)
 6 {
 7     return fa[x]==x?x:fa[x]=find(fa[x]);
 8 }
 9 void Union(int x,int y)
10 {
11     int f1=find(x);
12     int f2=find(y);
13     if(f1!=f2) fa[f1]=f2;
14 }
15 int main()
16 {
17     scanf("%d%d",&n,&m);
18     for(int i=1;i<=3*n;i++) fa[i]=i;
19     for(int i=1;i<=m;i++)
20     {
21         int num,a,b;
22         scanf("%d%d%d",&num,&a,&b);
23         if(a<1||a>n||b<1||b>n)
24             {ans++;continue;}
25         if(num==2&&a==b)
26             {ans++;continue;}
27         if(num==1)
28         {
29             if(find(a)==find(b+n)||find(a)==find(b+2*n)) ans++;
30             else
31             {
32                 Union(a,b);
33                 Union(a+n,b+n);
34                 Union(a+2*n,b+2*n);
35             }
36         }
37         else if(num==2)
38         {
39             if(find(a)==find(b)||find(a)==find(b+2*n)) ans++;
40             else
41             {
42                 Union(a,b+n);
43                 Union(a+n,b+2*n);
44                 Union(a+2*n,b);
45             }
46         }
47     }
48     printf("%d
",ans);
49     return 0;
50 }