POJ 2492. 并查集
原题链接
简单
作者:
史一帆
,
2021-05-18 21:15:56
,
所有人可见
,
阅读 168
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2010;
int p[N * 2]; // 1到n为一类(同一性别) n+1到2n为另一类(同一性别)
int t, n, m;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (x != y) p[x] = y;
}
int main()
{
scanf("%d", &t);
for (int i = 1; i <= t ; i ++ )
{
int flag = 0;
memset(p, 0, sizeof p);
scanf("%d%d", &n, &m);
for (int j = 1; j <= n * 2; j ++ ) p[j] = j;
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
int fa = find(a), fb = find(b);
if (fa == fb) flag = 1;
else
{
merge(a + n, b);
merge(a, b + n);
}
}
printf("Scenario #%d:\n",i);
if(flag == 1) printf("Suspicious bugs found!\n\n");
else printf("No suspicious bugs found!\n\n");
}
return 0;
}