欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA11396 Claw Decomposition(二分图判定)

程序员文章站 2022-06-02 20:29:47
...

题目链接:
UVA
洛谷

题目大意:
给定一个无向图,每个点的度数为3,判断是否能分解成若干个 爪 。每个点可以属于多个爪,每条边只能属于一个爪。
爪如图所示:
UVA11396 Claw Decomposition(二分图判定)
题解:
每个点的度数为3,这个条件很重要。画图分析会发现,如果一个图可以分解成若干个爪,任意一个作为爪中心的点,它的所有相邻的点都是爪的边缘;作为爪的边缘的点,它的所有相邻的点都是爪的中心。并且作为爪的中心和边缘的点可以同时互换。
然后这就是个二分图了。
所以这题只需要判断是不是二分图就没了。

AC代码 和 一些测试数据

代码:

#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define ULL unsigned long long
#define UI unsigned int
#define PII pair<int,int>
#define MPII(x,y) pair<int,int>{x,y}
#define _for(i,j,k) for(int i=j;i<=k;i++)
#define for_(i,j,k) for(int i=j;i>=k;i--)
#define efor(i,u) for(int i=head[u];i;i=net[i])
#define lowbit(x) (x&-x)
#define ls(x) x<<1
#define rs(x) x<<1|1
#define inf 0x3fffffff
//#pragma comment(linker, "/STACK:10240000000,10240000000")
using namespace std;
const int maxn = 2e6 + 5;
const int M = 1e9 + 7;
inline int mad(int a,int b){return (a+=b)>=M?a-M:a;}
int n,head[maxn],e[maxn],net[maxn],cnt;
void add(int u,int v){
	e[++cnt]=v;
	net[cnt]=head[u];
	head[u]=cnt;
}
int color[maxn];//0未着色,1和2着色 
bool bip(int u){
	for(int i=head[u];i;i=net[i]){
		if(color[u]==color[e[i]]) return false;
		if(!color[e[i]]){
			color[e[i]]=3-color[u];
			if(!bip(e[i])) return false;
		}
	}
	return true;
}
bool sol(){
	_for(i,1,n) color[i]=0;
	_for(i,1,n){
		if(!color[i]){
			color[i]=1;
			if(!bip(i)) return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	while(cin>>n,n){
		int u,v;
		while(cin>>u>>v,u|v){
			add(u,v);
			add(v,u);
		}
		if(sol()){
			puts("YES");
		}
		else puts("NO");
		_for(i,1,n) head[i]=0;
		cnt=0;
	}
	return 0;
}
相关标签: UVA 二分图