当前位置: 代码迷 >> 综合 >> POJ 2492 A Bug's Life .
  详细解决方案

POJ 2492 A Bug's Life .

热度:102   发布时间:2023-09-23 09:01:26.0

POJ 1182 食物链 * 的简易版本

此题目POJ题目地址

这类问题共同点就是 1)分为固定几类,2)有类似一个环 男-->女--> 男

要点就是:1)思考集合与集合合并的时候两个根的关系

                 2)结点压缩的时候,结点与根的关系怎么根据边递推上去


#include<iostream>
#include<cstdio>
#include<queue>
#include<map> 
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2000+5;
int p[maxn],r[maxn];
int getParent(int x){if(p[x]==x) return x;int xp=getParent(p[x]);r[x]=(r[x]+r[p[x]])%2;return p[x]=xp;
}
void merge(int xp,int yp,int x,int y)  //x与y 一定不同所以要 +1 
{p[xp]=yp;r[xp]=(r[y]+r[x]+1)%2;
}
int main()
{int T,kase=0;scanf("%d",&T);while(T--){int N,A,ok=1;scanf("%d%d",&N,&A);for(int i=1;i<=N;i++) {r[i]=0;p[i]=i;}int x,y,xp,yp;while(A--){scanf("%d%d",&x,&y);xp=getParent(x);yp=getParent(y);	if(xp!=yp) merge(xp,yp,x,y);else if(r[x]==r[y]) ok=0;          //忘加else结果一直WR } printf("Scenario #%d:\n%s\n\n",++kase,ok?"No suspicious bugs found!":"Suspicious bugs found!");}return 0;
}


  相关解决方案