题目链接
题目描述
-
有两种性别的虫子。它们只能不同性别间交配。给出一堆虫子的交配列表。判断是否满足只能在不同性别间交配的命题。
解题思路
- 利用带权并查集，把可以判断出性别关系的虫子放到同一集合中。
- 在Merge()和GetRoot()函数中更新子结点与根节点的性别关系。
-
性别关系类似于向量加减，可通过画向量图的方式计算结点间的关系。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
using namespace std;
const int MAXN = 2010;
int par[MAXN];//par[i]是i的根节点
int rea[MAXN];//rea[i]是i和根节点的关系,0是同性，1是异性
int GetRoot(int a, int r);
void Merge(int a, int b, int r);
bool Query(int a, int b);
int n, m;//n个虫子，m个操作
int main()
{
int k;
scanf("%d", &k);
int kase = 0;
while(k--){
++kase;
int i, r, x, y;
bool flag = 0;
scanf("%d%d", &n, &m);
for(i = 0;i <= n; ++i){
par[i] = i;
rea[i] = 0;
}
for(i = 0;i < m; ++i){
scanf("%d%d", &x, &y);
if(!Query(x, y)){
Merge(x, y, 1);
}
else{
if(rea[x] == rea[y]){
flag = 1;
}
}
}
printf("Scenario #%d:\n", kase);
if(flag) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
printf("\n");
}
}
int GetRoot(int a)
{
if(par[a] == a)
return a;
int pa = GetRoot(par[a]);
rea[a] = (rea[par[a]] + rea[a])%2;
par[a] = pa;
return pa;
}
void Merge(int a, int b, int r)
{
int pa = GetRoot(a);
int pb = GetRoot(b);
if(pa != pb){
par[pb] = pa;
rea[pb] = (rea[a] - r - rea[b] + 4) % 2;
}
return ;
}
bool Query(int a, int b)
{
return GetRoot(a) == GetRoot(b);
}