POJ 2492 A Bug's Life——并查集

POJ 2492 A Bug's Life——并查集

题意：两个集合，T组数据，每组数据以N M开头，表示有编号从1到n的n个物品以及m个条件，每个条件给出两个数a b，表示a b不在同一集合，如果所有的a b都不在同一集合那么没有BUG，否则有BUG

思路：参考​​poj1703​​，本题是poj1703的简化版

#include #include #include #include using namespace std;const int maxn = 2 * 1e5 + 10;int T, N, M, par[maxn], ran[maxn];void Init() { for (int i = 0; i <= (N<<1); i++) par[i] = i, ran[i] = 0;}int Query(int x) { return par[x] == x ? x : par[x] = Query(par[x]); }void Union(int x, int y) { x = Query(x), y = Query(y); if (x == y) return; if (ran[x] < ran[y]) par[x] = y; else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; }}bool Same(int x, int y) { return Query(x) == Query(y);}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &N, &M); Init(); bool ok = true; while (M--) { int a, b; scanf("%d%d", &a, &b); bool ok1 = Same(a, b), ok2 = Same(a + N, b), ok3 = Same(a, b + N); if (ok1 && !ok2 && !ok3) ok = false; if (ok) { Union(a + N, b); Union(a, b + N); } } printf("Scenario #%d:\n", kase); if (!ok) printf("Suspicious bugs found!\n\n"); else printf("No suspicious bugs found!\n\n"); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。