思路：见代码吧。
#include#include #include #include #include using namespace std;const int maxn=2010;int n,m;int father[maxn];int num[maxn]; //num[i]表示int rel[maxn]; //rel[i]表示它与根节点的关系，0代表同性，1代表异性void init(){ for(int i=0;i<=n;i++){ father[i]=i; num[i]=1; rel[i]=0; }}//查找根节点时，同时更新它与根节点的关系。这里要注意的是：先更新玩父节点，再更新自己的。int find_root(int x){ int fa; if(father[x]==x) return x; fa=find_root(father[x]); rel[x]=(rel[x]+rel[father[x]])%2; father[x]=fa; return father[x];}void Union(int a,int b,int x,int y){ if(num[x]>num[y]){ father[y]=x; num[x]+=num[y]; //更新y与根节点x的关系 rel[y]=(rel[b]+1+rel[a])%2; //刚开始这里写错了，忘加了rel[a]。。。下面忘加了rel[b]。。。 } else{ father[x]=y; num[y]+=num[x]; //更新x与根节点y的关系 rel[x]=(rel[a]+1+rel[b])%2; }}int main(){ int t,a,b,flag; scanf("%d",&t); for(int q=1;q<=t;q++){ scanf("%d%d",&n,&m); init(); flag=0; for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); if(flag) continue; int x=find_root(a); int y=find_root(b); if(x!=y){ Union(a,b,x,y); } else{ //当a、b父节点相同时： //t表示a、b之间的关系，若关系为0，就表示它们是同性 //也可以判断两者与父节点性别的区别是相同的，即rel[a]==rel[b]那么这两个为同性 int t=(rel[b]+rel[a])%2; if(t==0){ flag=1; } } } printf("Scenario #%d:\n",q); if(flag){ printf("Suspicious bugs found!\n"); } else{ printf("No suspicious bugs found!\n"); } printf("\n"); } return 0;}