NYOJ42 一笔画问题

NYOJ42 一笔画问题,第1张

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=42

题目分析:
要能一笔画化成需要同时满足两个以下条件:
1)该图是连通的。
2)图中奇点的个数是2或者0。

参考代码:

#include<stdio.h>
#include<string.h>

int set[1001];

int find(int k)
{
	int r = set[k];
	while(r != set[r])
		r = set[r];
	return r;
}

void merge(int r1, int r2)
{
	if(r1 < r2)
		set[r2] = r1;
	else
		set[r1] = r2;
}

int main()
{
	bool used[1001];
	int count[1001];
	int t,i;
	int a,b,c;
	int p,q;
	int r1,r2;
	int ans;
	scanf("%d", &t);
	while(t--)
	{
		memset(count, 0, sizeof(count));
		memset(used, 0, sizeof(used));
		scanf("%d %d", &p, &q);
		for(i = 0; i <= q; ++i)
			set[i] = i;

		c = 0;
		for(i = 0; i < q; ++i)
		{
			scanf("%d %d", &a, &b);
			if(!used[a])
			{
				++c;
				used[a] = true;
			}
			if(!used[b])
			{
				++c;
				used[b] = true;
			}
			r1 = find(a);
			r2 = find(b);
			if(r1 != r2)
			{
				merge(r1,r2);
				--c;
			}
			++count[a];
			++count[b];
		}

		ans = 0;
		for(i = 1; i <= p; ++i)
		{
			if(!used[i])
				++c;
			if(count[i] & 1)
				++ans;
		}

		if(c <= 1 && (ans == 2 || ans == 0))
			printf("Yes\n");
		else
			printf("No\n");		
	}
}   


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/2084043.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-07-22
下一篇 2022-07-22

发表评论

登录后才能评论

评论列表(0条)

保存