给一个无向图，判断是否为二分图 是否有奇环。用染色法解决，也可以用并查集解决，时间复杂度是相同的，但是并查集用的内存少。
这里给出Bfs染色的代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=2000+1,maxm=1e+6; int color[maxn]; vector<int>adj[maxn]; bool isbipart(int s,vector<int>connect[]) { color[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int now=q.front();q.pop(); for(int i=0;i<connect[now].size();i++) { int next=connect[now][i]; if(color[next]==0) { if(color[now]==1)color[next]=2; else color[next]=1; q.push(next); continue; } if(color[next]==color[now])return false; } } return true; } int main() {freopen("t.txt","r",stdin); int T;scanf("%d",&T); int tt=T; while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) {color[i]=0;adj[i].clear();} int a,b; for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); adj[a].push_back(b); adj[b].push_back(a); } bool ans=true; for(int i=1;i<=n&&ans;i++) { if(color[i]==0)ans=isbipart(i,adj); } if(ans)printf("Scenario #%d:\nNo suspicious bugs found!\n",tt-T); else printf("Scenario #%d:\nSuspicious bugs found!\n",tt-T); if(T>0)printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/heisenberg-/p/6506424.html
