首页 > 代码库 > 染色法判断二分图
染色法判断二分图
染色法判断二分图
给一个无向图,判断是否是二分图。
这很简单:
1.把节点1染为1。
2.搜索各点,遍历与此点u相连的点v。
3.如果点v没颜色,把它染为与点u相反的颜色(即-u)。
4.如果有颜色,则比较v与u颜色是否相同。若相同,返回0;若不同,则继续。
代码:
1 #include<cstdio> 2 #define N 420000 3 int head[N],next[N],to[N],rs[N],n,m,a,b,y,num; 4 int dfs(int x){ 5 for(int i=head[x];i;i=next[i]){ 6 y=to[i]; 7 if(rs[y]==rs[x]) 8 return 0; 9 if(!rs[y]) 10 rs[y]=-rs[x]; 11 } 12 return 1; 13 } 14 int main(){ 15 scanf("%d%d",&n,&m); 16 if(n==1){ 17 printf("NO"); 18 return 0; 19 } 20 for(int i=1;i<=m;++i){ 21 scanf("%d%d",&a,&b); 22 next[++num]=head[a]; 23 to[num]=b; 24 head[a]=num; 25 } 26 rs[1]=1; 27 for(int i=1;i<=n;++i){ 28 if(!dfs(i)){ 29 printf("NO"); 30 return 0; 31 } 32 } 33 printf("YES"); 34 return 0; 35 }
不过代码不一定对,反正自己测得几组数是都对了。
染色法判断二分图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。