首页 > 代码库 > 二分图染色法查找增广轨

二分图染色法查找增广轨

 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<string.h> 5 using namespace std; 6 int  mp[1004][1004]; 7 int n,m; 8 int col[1004]; 9 bool isbg;10 void dfscol(int i,int c){///i代表结点,c代表颜色11 if(!isbg)return ;12 col[i]=c;///染色13 for(int j=1;j<=n;j++){14     if(mp[i][j]){///查找相邻的边15         if(col[j]==-1)///相邻的边没有被染过色16         dfscol(j,c^1);///染上不同的颜色来区分,1^1=0,0^1=117         else if(col[j]==c){///如果出现相邻点颜色相同18             isbg=false;19             return ;20         }21     }22 }23 return ;24 }25 bool judge(){26 isbg=true;27 for(int i=1;i<=n;i++){28 if(col[i]!=-1)continue;///如果该点已经被染过色,那么继续查找 下一个结点29 dfscol(i,1);///用1和0来表示染色,先用1开始染色30 if(isbg==false)break;31 }32 return isbg;33 }34 int main()35 {36     int m,n;37     int x,y;38     while(cin>>n>>m){///n个点,m组边39             memset(mp,0,sizeof(mp));40         for(int i=1;i<=m;i++){41             cin>>x>>y;42             mp[x][y]=1;43             mp[y][x]=1;44         }45     isbg=true;46     memset(col,-1,sizeof(col));///用来标记点是否被访问过47     if(!judge()){48         cout<<"No\n";49         continue;50     }51     else cout<<"Yes\n";52     }53     return 0;54 }

 

二分图染色法查找增广轨