首页 > 代码库 > 二分图染色法查找增广轨
二分图染色法查找增广轨
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 }
二分图染色法查找增广轨
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。