经典的并查集问题

对于这种问题，并查集需要分类

开3*n的并查集，其中x用来连接与x同类的，x+n用来连接x吃的，x+2*n用来连接x被吃的。

1 x y时，如果 x吃y 或 x被y吃，那么为假话，

否则x与y同类，x吃的y也吃，x被吃的y也被吃；

2 x y时，如果 x与y同类（x与x自然也是同类）或 y吃x，那么为假话，

否则x吃y，y被x吃，y吃x被吃的.

——代码

 #include <cstdio>

 #include <iostream>

 #define N 1000001

 int n, k, ans;

 int f[N];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int find(int x)

 {

     return x == f[x] ? x : f[x] = find(f[x]);

 }

 inline void connect(int x, int y)

 {

     x = find(x);

     y = find(y);

     if(x ^ y) f[x] = y;

 }

 int main()

 {

     int i, j, x, y, z;

     n = read();

     k = read();

     for(i = ; i <=  * n; i++) f[i] = i;

     for(i = ; i <= k; i++)

     {

         z = read();

         x = read();

         y = read();

         if(x > n || y > n)

         {

             ans++;

             continue;

         }

         if(z == )

         {

             if(find(x + n) == find(y) || find(x +  * n) == find(y))

             {

                 ans++;

                 continue;

             }

             connect(x, y);

             connect(x + n, y + n);

             connect(x +  * n, y +  * n);

         }

         else

         {

             if(find(x) == find(y) || find(x +  * n) == find(y))

             {

                 ans++;

                 continue;

             }

             connect(x + n, y);

             connect(y +  * n, x);

             connect(y + n, x +  * n);

         }

     }

     printf("%d\n", ans);

     return ;

 }

还有带权并查集的做法

这道题的特殊之处在于对于任意一个并查集，只要告诉你某个节点的物种，你就可以知道所有节点对应的物种。

比如一条长为4的链甲->乙->丙->丁，我们知道乙是A物种。那么甲一定是B物种，因为A只吃B物种，不吃C物种或是自己的同类。同样的丙一定是C物种，丁是B物种。

也就是说，每一条链上都是A、B、C物种循环，这也是我们寻找不合逻辑的假话的出发点。

我们可以定义数组d[i]表示节点i到根节点距离mod3的结果帮助解题。

我们统计谎话的数量，那么我们把谎话这样分类：

第一类叫弱智的谎话，包括

（1）自己吃自己的同类是谎话，表述为d==2&&x==y（其中x y是我们读入的量）；

（2）编号超出限制，表述为x>n||y>n。第二类叫不弱智的谎话，包括d==1和d==2这样两类。

（1）d==1。

我们先要考虑x y是否在同一个并查集中，这是判断真假话的前提。

如果x y 不在同一个并查集中，那么关于他们的任何表述都可以是真的。

比如两条链：1->2->3->4->5 6->7->8->9

如果我说1和6是同类，那么自然地，2与7，3与8，4与9成为同类。

我们任意的选取两个数是同类都是符合的。

下面我们要做的就是把两个并查集合并。

d[f[x]]=(d[y]-d[x]+3)%3;//关于距离

f[f[x]]=f[y];//关于父亲

如果x y在同一个并查集中，那么违反距离关系的话一定是假话。

d[x]!=d[y]//关于距离

（2）d==2。

还是先看x y是否在一个并查集中，如果不在，那么合并并查集；如果在，那么根据距离关系找出假话。

——代码

 #include <cstdio>

 #include <iostream>

 #define N 1000001

 int n, k, ans;

 int f[N], d[N];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int find(int x)

 {

     if(x ^ f[x])

     {

         int fx = f[x];

         f[x] = find(f[x]);

         d[x] = (d[x] + d[fx]) % ;

     }

     return f[x];

 }

 int main()

 {

     int i, j, x, y, z;

     n = read();

     k = read();

     for(i = ; i <= n; i++) f[i] = i;

     for(i = ; i <= k; i++)

     {

         z = read();

         x = read();

         y = read();

         if(x > n || y > n)

         {

             ans++;

             continue;

         }

         if(z == )

         {

             if(find(x) == find(y))

             {

                 if(d[x] ^ d[y]) ans++;

             }

             else

             {

                 d[f[x]] = (d[y] - d[x] + ) % ;

                 f[f[x]] = f[y];

             }

         }

         else

         {

             if(find(x) == find(y))

             {

                 if(d[x] ^ ((d[y] + ) % )) ans++;

             }

             else

             {

                 d[f[x]] = (d[y] - d[x] + ) % ;

                 f[f[x]] = f[y];

             }

         }

     }

     printf("%d\n", ans);

     return ;

 }

最后是关于合并两个根时两根之间的距离的解释:

设合并后两根距离为a(即要求的量）

R[i]表示点i到他们原来祖先的距离，途中所有线段长都可以表示。

注意每条边的长度是不一样的，∴R[x]+a-R[y]≠R[x]，而等于x、y的距离即食物关系（大家可以往下翻，下面有关于这个的讲解）

设该距离为t

方程：R[x]+a-R[y]=t，整理得a=t-R[x]+R[y],当然把x与y换一下也是成立的，这取决于你的程序。

巴特西

[luoguP2024] 食物链（并查集）

设合并后两根距离为a(即要求的量）

方程：R[x]+a-R[y]=t，整理得a=t-R[x]+R[y],当然把x与y换一下也是成立的，这取决于你的程序。

最新文章

热门文章