poj 1182 并查集 食物链类

本文主要是介绍poj 1182 并查集 食物链类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

有n只动物，分别编号1....n。所有动物都属于A，B，C中的一种，已知A吃B，B吃C，C吃A。

按顺序给出下面两种共K条信息：

1. x 和 y 属于同一类。

2. x 吃 y 。

然而这些信息可能会出错，有可能有的信息和之前给出的信息矛盾，也有的信息可能给出的 x 和 y 不在n的范围内。

求k条信息中有多少条是不正确的。

解析：

对于每只动物，创建3个元素 i - A， i - B， i - C，用这 3 * n个元素建立并查集。

i - x 表示 “i属于种类x”；

并查集里面的每一个组（连通区域）表示组内所有元素代表的情况都同时发生或者同时不发生。

所以，第一种信息：x和y属于同一类，合并 x - A， y - A、 x - B，y - B，x - C，y - C，就行了。

对于第二种信息：x 吃 y ， 只要合并 x - A，y - B， x - B，y - C， x - C， y - A，就行了。

代码：

（加Rank，，，慢了一点）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50000 * 3 + 10;
const double eps = 1e-9;int fa[maxn];
int Rank[maxn];void Init(int n)
{for (int i = 0; i < n; i++){fa[i] = i;Rank[i] = 0;}
}int Find(int x)
{if (fa[x] != x)fa[x] = Find(fa[x]);return fa[x];
}void Union(int u, int v)
{int fau = Find(u);int fav = Find(v);if (fau == fav)return;if (Rank[fau] < Rank[fav]){fa[fau] = fav;}else{fa[fav] = fau;if (Rank[fau] == Rank[fav])Rank[fau]++;}
}bool same(int u, int v)
{return Find(u) == Find(v);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint n, k;scanf("%d%d", &n, &k);Init(n * 3);int ans = 0;for (int i = 0; i < k; i++){int op, x, y;scanf("%d%d%d", &op, &x, &y);x--, y--;if (x < 0 || n <= x || y < 0 || n <= y){ans++;continue;}if (op == 1){
///（x属于A， y属于B） （x属于A， y属于B）    都是和x，y属于同一类矛盾的。
if (same(x, y + n) || same(x, y + 2 * n)){ans++;}else{Union(x, y);Union(x + n, y + n);Union(x + 2 * n, y + 2 * n);}}else///op == 2{
/// （x属于A，y属于A）   （x属于A，y属于C）   都是和 x 吃 y 矛盾的
if (same(x, y) || same(x, y + 2 * n)){ans++;}else{Union(x, y + n);Union(x + n, y + 2 * n);Union(x + 2 * n, y);}}}printf("%d\n", ans);return 0;
}

不加rank，快了饿一点：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 50000 * 3 + 10;
const double eps = 1e-9;int fa[maxn];void Init(int n)
{for (int i = 0; i < n; i++){fa[i] = i;}
}int Find(int x)
{if (fa[x] != x)fa[x] = Find(fa[x]);return fa[x];
}void Union(int u, int v)
{int fau = Find(u);int fav = Find(v);if (fau != fav){fa[fav] = fau;}
}bool same(int u, int v)
{return Find(u) == Find(v);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint n, k;scanf("%d%d", &n, &k);Init(n * 3);int ans = 0;for (int i = 0; i < k; i++){int op, x, y;scanf("%d%d%d", &op, &x, &y);x--, y--;if (x < 0 || n <= x || y < 0 || n <= y){ans++;continue;}if (op == 1){if (same(x, y + n) || same(x, y + 2 * n)){ans++;}else{Union(x, y);Union(x + n, y + n);Union(x + 2 * n, y + 2 * n);}}else///op == 2{if (same(x, y) || same(x, y + 2 * n)){ans++;}else{Union(x, y + n);Union(x + n, y + 2 * n);Union(x + 2 * n, y);}}}printf("%d\n", ans);return 0;
}

这篇关于poj 1182 并查集 食物链类的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---