题解：UVA11396 Claw Decomposition

做法

对于每一个爪，我们发现有

1

个点度为

3

，剩下

3

个点度为

1

，我们不妨将度为

3

的点当作根，度为

1

的点当作叶子，如下图：

当多个爪连在一起，我们就会发现，

1

个根一定连着

3

个叶子，

1

个叶子一定连着

3

个根，如下图：

所以我们就可以用 dfs 进行交替染色，如果在搜索过程中发现一个点既为根又为叶子，就说明该图不是爪图。

在学完二分图后我们也能发现在一个爪图中仅有根和叶子两个集合，所以本题也可以被视为一道关于二分图的判定的题目。

代码

注：由于本蒟蒻并没有 UVA 的号所以无法验证代码的正确性，仅供参考。

CPP

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int a,b;
int num[1805],pre[1805],last[305],cnt;
int cntw,cntb;
int t[305],c[305];
int fla;
void ddxyz(){
	cnt=0;
	fla=0;
	for(int i=1;i<=n;i++){
		last[i]=0;
		t[i]=0;
		c[i]=0;
	}
}
void add(int x,int y){
	++cnt;
	num[cnt]=y;
	pre[cnt]=last[x];
	last[x]=cnt;
}
void dfs(int xy,int col){
	t[xy]=1;
	c[xy]=col;
	if(col==1){
		cntw++;
	}
	else{
		cntb++;
	}
	if(col==1){
		col=2;
	}
	else{
		col=1;
	}
	for(int i=last[xy];i;i=pre[i]){
		if(t[num[i]]==0){
			dfs(num[i],col);
			if(fla==1){
				return ;
			}
		}
		else{
			if(col!=c[num[i]]){
				fla=1;
				return ;
			}
		}
	}
}
int main(){
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		ddxyz();
		while(1){
			scanf("%d%d",&a,&b);
			if(a==0&&b==0){
				break;
			}
			add(a,b);
			add(b,a);
		}
		for(int i=1;i<=n;i++){
			if(t[i]==0){
				cntw=0;
				cntb=0;
				dfs(i,1);
				if(fla==1){
					printf("NO\n");
					break;
				}
			}
		}
		if(fla==0){
			printf("YES\n");
		}
	}
	return 0;
}

题解：UVA11396 Claw Decomposition

文章操作

做法

代码

相关推荐

评论

题解：UVA11396 Claw Decomposition