首页 > 代码库 > UVa 11396 爪分解（二分图判定）
UVa 11396 爪分解（二分图判定）
https://vjudge.net/problem/UVA-11396
题意：
给出n个结点的简单无向图，每个点的度数均为3。你的任务是判断能否把它分解成若干爪。每条边必须属于一个爪，但同一个点可以出现在多个爪里。
思路：
一个鸡爪当中，有一个中心点，即度为3的点，还有3个边缘点。
每条边都连接了一个中心点和一个边缘点，于是就是二分图判定。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map>10 using namespace std;11 12 const int maxn=300+5;13 14 vector<int> G[maxn];15 int color[maxn];16 17 bool bipartite(int u)18 {19 for(int i=0;i<G[u].size();i++)20 {21 int v=G[u][i];22 if(color[v]==color[u]) return false;23 if(color[v]==0)24 {25 color[v]=3-color[u];26 if(!bipartite(v)) return false;27 }28 }29 return true;30 }31 32 int n;33 34 int main()35 {36 //freopen("D:\\input.txt","r",stdin);37 while(~scanf("%d",&n) && n)38 {39 for(int i=1;i<=n;i++) G[i].clear();40 int u,v;41 while(true)42 {43 scanf("%d%d",&u,&v);44 if(u==0 && v==0) break;45 G[u].push_back(v);46 G[v].push_back(u);47 }48 memset(color,0,sizeof(color));49 color[1]=1;50 bool flag = bipartite(1);51 if(flag) puts("YES");52 else puts("NO");53 }54 return 0;55 }
UVa 11396 爪分解（二分图判定）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。