此题可用并查集过。
不过为了学习二分图。来做的这道题。
二分图的检测核心就是染色法,将路径两端点染上不同的颜色(即不同的标记),如果某一点存在矛盾(即标记不同),即非二分图。。。
遍历搜索所有点边即可。。
代码如下:
#include<stdio.h> #include<string.h> #include<vector> using namespace std; vector <int> map[2002]; int link[2002]; int vis[2002]; int n,k; int dfs(int a) { vis[a]=1; int l=map[a].size(); for(int i=0; i<l; i++) { int z=map[a][i]; if(link[a]==link[z]) return 0; if(link[z]==-1) { link[z]=link[a]?0:1; if(!dfs(z)) return 0; } } return 1; } int main() { int t; int cnt=0; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); memset(link,-1,sizeof(link)); int n,k; scanf("%d%d",&n,&k); while(k--) { int a,b; scanf("%d%d",&a,&b); map[a].push_back(b); map[b].push_back(a); } int flag=0; for(int i=1; i<=n; i++) if(!vis[i]) { link[i]=1; if(!dfs(i)) { flag=1; break; } } printf("Scenario #%d:\n",++cnt); if(!flag) printf("No s"); else printf("S"); printf("uspicious bugs found!\n"); if(t) printf("\n"); } return 0; }