首页 > 代码库 > SGU 172.eXam

SGU 172.eXam

2024-07-17 19:28:13   212人阅读

时间限制：0.25s

空间限制：4M

题意：

       将n（n<200）个点分成两个集合，给出m(m<=30000)对不能在一个集合的点对，判断能否分成满足要求的集合，输出其中一个集合和集合的总数目。

 

 

 

 

 

 

Solution：

              二分图染色，dfs即可。

 

#include <iostream>#include <cstring>#include <cstdio>using namespace std;int n,m,x,y,tol;bool g[209][209];int f[30009];int dfs(int x){       for(int i=1;i<=n;i++){              if(!g[x][i]) continue;              if(f[i]==-1){                     f[i]=!f[x];                     if(f[i]==0) tol++;                     if(dfs(i)) return 1;              }              else                     if(f[i]==f[x])                            return 1;       }       return 0;}int main(){       scanf("%d %d",&n,&m);       memset(g,0,sizeof g);       memset(f,-1,sizeof f);       for(int i=1;i<=m;i++){              scanf("%d %d",&x,&y);              g[x][y]=g[y][x]=1;       }       for(int i=1;i<=n;i++){              if(f[i]!=-1) continue;              f[i]=0,tol++;              if(dfs(i)){                     puts("no");                     return 0;              }       }       printf("yes\n%d\n",tol);       for(int i=1;i<=n;i++)              if(f[i]==0) printf("%d ",i);       return 0;}

 

　　

 


联系
我们