博客

题目链接：https://vjudge.net/problem/UVA-10054

题目大意：给出一串数，要求相邻两组数的第一组的第二个数与第二组的第一个数相等，并且，第一组的第一个数要与第n组的第二个数相等。

题解：典型的欧拉回路，并输出欧拉回路的路径问题。

欧拉回路的条件：没有奇度节点的连通图。

记录欧拉回路的路径，用栈记录，先进后出。

代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
const int maxn=50;
const int M=60;
int mp[M][M];
int degree[M];
struct note
{
	int x,y;
} li;
stack<note> q;
void oula(int a)
{
	int i,j,k;
	for(i=1; i<=maxn; i++)
	{
		if(mp[a][i])
		{
			mp[a][i]--;
			mp[i][a]--;
			oula(i);
			li.x=a;
			li.y=i;
			q.push(li);
		}
	}
}
void solve()
{
	int i,j,k;
	int flag=0;
	for(i=1; i<=maxn; i++)
	{
		for(j=1; j<=maxn; j++)
		{
			if(mp[i][j])
			{
				flag=1;
				break;
			}
		}
		if(flag)
			break;
	}
	if(flag)
		oula(i);
	while(!q.empty())
	{
		li=q.top();
		printf("%d %d\n",li.x,li.y);
		q.pop();
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	int ans=0;
	while(t--)
	{
		ans++;
		memset(mp,0,sizeof(mp));
		memset(degree,0,sizeof(degree));
		int n;
		int a,b;
		scanf("%d",&n);
		int i,j,k;
		for(i=1; i<=n; i++)
		{
			scanf("%d%d",&a,&b);
			mp[a][b]++;
			mp[b][a]++;
			degree[a]++;
			degree[b]++;
		}
		int flag=0;
		for(i=1; i<=maxn; i++)//一共有50个颜色
		{
			if(degree[i]%2!=0)
			{
				flag=1;
				break;
			}
		}
		if(ans>1)
			printf("\n");
		if(flag)
		{
			printf("Case #%d\n",ans);
			printf("some beads may be lost\n");
		}
		else
		{
			printf("Case #%d\n",ans);
			solve();
		}
	}
	return 0;
}