首页 > 代码库 > [luoguP2024] 食物链（并查集）
[luoguP2024] 食物链（并查集）
传送门
经典的并查集问题
对于这种问题，并查集需要分类
开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被吃的.
——代码
1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4 5 int n, k, ans; 6 int f[N]; 7 8 inline int read() 9 {10 int x = 0, f = 1;11 char ch = getchar();12 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14 return x * f;15 }16 17 inline int find(int x)18 {19 return x == f[x] ? x : f[x] = find(f[x]);20 }21 22 inline void connect(int x, int y)23 {24 x = find(x);25 y = find(y);26 if(x ^ y) f[x] = y;27 }28 29 int main()30 {31 int i, j, x, y, z;32 n = read();33 k = read();34 for(i = 1; i <= 3 * n; i++) f[i] = i;35 for(i = 1; i <= k; i++)36 {37 z = read();38 x = read();39 y = read();40 if(x > n || y > n)41 {42 ans++;43 continue;44 }45 if(z == 1)46 {47 if(find(x + n) == find(y) || find(x + 2 * n) == find(y))48 {49 ans++;50 continue;51 }52 connect(x, y);53 connect(x + n, y + n);54 connect(x + 2 * n, y + 2 * n);55 }56 else57 {58 if(find(x) == find(y) || find(x + 2 * n) == find(y))59 {60 ans++;61 continue;62 }63 connect(x + n, y);64 connect(y + 2 * n, x);65 connect(y + n, x + 2 * n);66 }67 }68 printf("%d\n", ans);69 return 0;70 }
还有带权并查集的做法
正在努力学习。。
[luoguP2024] 食物链（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。