P2024 食物链（种类并查集||带权并查集）

先写所谓的种类并查集。

就是开3*n的空间，前n为A，后边依次是B，C

食物链为A->B->C->A

对于每句话都是先判断是否合法，然后在改并查集就好了

 1 #include<iostream>
 2 #include<fstream>
 3 using namespace std;
 4 const int N=5e4+100;
 5 int fa[N*3];
 6 int finds(int x)//正常的并查集find函数
 7 {
 8     while(fa[x]!=x)
 9     {
10         x=fa[x];
11     }
12     return x;
13 }
14 int main(void)
15 {
16 //    ifstream in("eat.in");
17     int n,k;
18     cin>>n>>k;
19     for(int i=1;i<=3*n;i++)
20     {
21         fa[i]=i;
22     }
23     int ans=0;
24     for(int i=1;i<=k;i++)
25     {
26         int d,x,y;
27         cin>>d>>x>>y;
28         if(x<=0||y<=0||x>n||y>n)//存在不合法的编号就是假话
29         {
30             ans++;
31             continue;
32         }
33         if(d==1)//这句话说x和y是同类
34         {
35             if(finds(x+n)==finds(y)||finds(x)==finds(y+n))//如果x吃y或者y吃x
36             {
37                 ans++;
38             }
39             else//如果是合法的，那么就得把这句话所说的加入到并查集内
40             {
41                 fa[finds(x)]=finds(y);
42                 fa[finds(x+n)]=finds(y+n);
43                 fa[finds(x+2*n)]=finds(y+2*n);
44             }
45         }
46         else if(d==2)//这句话说x吃y
47         {
48             if(finds(x)==finds(y)||finds(x)==finds(y+n))//如果xy同类或者y吃x
49             {
50                 ans++;
51             }
52             else//如果合法，就得把这句话所说的加入到并查集内
53             {
54                 fa[finds(x+n)]=finds(y);
55                 fa[finds(x+n+n)]=finds(y+n);
56                 fa[finds(x)]=finds(y+n+n);
57             }
58         }
59     }
60 //    ofstream out("eat.out");
61     cout<<ans<<endl;
62     return 0;
63 }

带权并查集有点像dp了，看命。。。

图来自https://blog.csdn.net/u013075699/article/details/80379263

可以得出r[z] = (r[x] + r[y]) % 3;也就是查找（顺便路径压缩的时候的r数组改变方式就有了）

然后再盗一张

这样一来合并的时候的r数组改变也就有了

 1 #include<iostream>
 2 #include<fstream>
 3 using namespace std;
 4 const int N=5e4+100;
 5 int fa[N];
 6 int r[N];//0表示同类，1表示父节点吃子结点，2表示子结点吃父节点
 7 int finds(int x)
 8 {
 9     while(fa[x]!=fa[fa[x]])//如果父节点还存在父节点，就继续往上
10     {
11         r[x]=(r[x]+r[fa[x]])%3;//更新关系，可从表中得出
12         
13         //在这里折磨了好久，不能先改fa[x],而要先改r数组
14         
15         fa[x]=fa[fa[x]];//越过父节点
16     }
17     return fa[x];
18 }//并查集finds函数
19 
20 void Union(int p,int q,int d)
21 {
22     int pRoot=finds(p);
23     int qRoot=finds(q);
24     if(pRoot==qRoot)
25     {
26         return ;
27     }
28     fa[qRoot]=pRoot;//将第二个集合并入第一个
29     //改权值
30     r[qRoot]=(r[p]-r[q]+3+(d-1))%3;
31 }
32 int main(void)
33 {
34 //    ifstream in("eat.in");
35     int n,k;
36     cin>>n>>k;
37     for(int i=1;i<=n;i++)
38     {
39         fa[i]=i;
40         r[i]=0;
41     }
42     int ans=0;
43     for(int i=1;i<=k;i++)
44     {
45         int d,x,y;
46         cin>>d>>x>>y;
47         if(x<=0||y<=0||x>n||y>n)
48         {
49             ans++;
50             continue;
51         }
52         if(finds(x)==finds(y))
53         {
54             if(d==1&&r[x]!=r[y])//说x和y是同类，但其实不是
55             {
56                 ans++;
57             }
58             if(d==2&&(r[x]+1)%3!=r[y])//说x吃y，但其实x并不吃y
59             {
60                 ans++;
61             }
62         }
63         else
64         {
65             Union(x,y,d);
66         }
67     }
68     cout<<ans;
69 //    ofstream out("eat.out");
70     return 0;
71 }