首页 > 代码库 > 【分解爪UVA11396-二分图染色模板】
【分解爪UVA11396-二分图染色模板】
·Rujia：“稍加推理即可解决该题……”
·英文题，述大意：
一张无向连通图，每个点连有三条边。询问是否可以将这个图分成若干个爪子，并满足条件：①每条边只能属于一个爪子②每个点属于几个爪子无所谓。输出YES/NO。
·注意一个关键条件：“每条边只能属于一个爪子”：
·注意一个逻辑顺序：
如果我们这样想，就很吃力：如何寻找一种划分方案，将原图划分为若干个爪子，如果无法划分，则输出NO。
所以换一下口味：只要这个图能够合法染色，那么必定存在一种分配情况使得这个图被分成若干个爪子。
·以此同时：题目中“每个点有三条边”使得这道题只需要对任意一个点判定一次染色就行了。
1 #include<stdio.h> 2 #include<cstring> 3 #define go(i,a,b) for(int i=a;i<=b;i++) 4 #define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v) 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 using namespace std;const int N=500; 7 struct E{int v,next;}e[N*N];int n,k,head[N],color[N]; 8 void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;} 9 bool Dye(int u){fo(i,head,u)10 {11 if(color[u]==color[v])return 0;12 if(!color[v]){color[v]=3-color[u];if(!Dye(v))return 0;}}return 1;13 }14 int main(){while(scanf("%d",&n)&&n)15 {16 k=1;mem(head,0);int u,v;17 while(scanf("%d%d",&u,&v)&&u&&v)ADD(u,v),ADD(v,u); 18 mem(color,0);color[1]=1;puts(Dye(1)?"YES":"NO");19 }return 0;}//Paul_Guderian
此刻我站在窗前望着外面，车辆穿梭高楼闪烁，
伴着晶莹的小雨和那歌声，我轻轻哼起这首歌。-------汪峰《生来孤独》
【分解爪UVA11396-二分图染色模板】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。