[置頂]NYOJ 42一筆画問題

タイトルリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=42
もうすぐ1周间ブログを书いたことがなくて、データ构造の中のアルゴリズムは多すぎて、経典のテーマはそんなに多くて、1つの少ないことをして、自分で学んだので、多くの时間をかけて理解しました....話はやめて....
考え方:簡単な欧拉回路は、1つの筆画が各点が連通しているかどうかを判断し、連通しているかどうかを判断し、集を調べて行うことができる.また,ノードが奇点の個数が0または2であれば1画である.
コード:

 
#include<stdio.h>
#include<string.h>
int a[5001],rank[5001],ans[5001];
int find(int x)/*           ,               */
{
	int temp;
	if(x==a[x]) return x;
	else return temp=find(a[x]);
}
void uni(int x,int y)/*  x,y       */
{
	if(rank[x]>rank[y])/*         ，         ,      wa   */
	{
		rank[x]++;
		a[y]=x;/*y x  ，    y     x*/
	}
	if(rank[x]<rank[y])
	{
		rank[y]++;
		a[x]=y;
	}
	if(rank[x]==rank[y])
	{
		rank[x]++;
		a[y]=x;
	}
}
void make_set()/*              */
{
	for(int i=0;i<=5000;i++)
	{
		a[i]=i;/*   ，            */
	}
}
int main()
{
	int ncases,n,m,x,y,i,j,count,jdcount;
	scanf("%d",&ncases);
	while(ncases--)
	{
		memset(rank,0,sizeof(rank));/*       */
		memset(ans,0,sizeof(ans));
		make_set();
		count=0;
		jdcount=0;
		scanf("%d %d",&n,&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d %d",&x,&y);
			ans[x]++;
			ans[y]++;
			x=find(x);/*  x   */
			y=find(y);/*  y   */
			if(x!=y)
			{
				uni(x,y);/*       ,            */
			}
		}
		for(i=1;i<=n;i++)/*         */
		{
			if(find(i)==i)/*          ，               ，        ，     */
			{
				count++;
			}
		}
		/*
		printf("
");
		printf("%d
",count);
		printf("
");
		*/
		for(i=1;i<=5000;i++)
		{
		    if(ans[i]%2==1)
		    {
		        jdcount++;
		    }
		}
		/*
		printf("
");
		printf("%d
",jdcount);
		printf("
");
		*/
		if((jdcount==0||jdcount==2)&&count==1)/*     0   2            */
		{
		    printf("Yes
");
		}
		else
		{
		    printf("No
");
		}
	}
	return 0;
}