uva 10054 The Necklace(オラ回路)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=116#problem/C
标题:カラービーズで結ばれたネックレスがあり、それぞれのビーズの半分が異なる色(1~50で各種の色を表す)で構成され、隣接する2つのビーズが接触する場所で色が同じである.今、こまごましたビーズをあげて、完全なネックレスに復元できるかどうかを確認します.
考え方:各ビーズの半分の色をノードと見なし、それらの間に無方向のエッジを作ります.n辺に変換してオーラ戻り路を構成できるかどうかの問題.
オーラ戻り路は、孤立ノード図Gが与えられ、回路が1つ存在する場合、図中の各辺を1回かつ1回のみ通過する.定義から分かるように、オーラループは、最初の図の連通が存在し、各ノードの度数は偶数である.これに基づいてdfsでパスを印刷します.
この問題のデータはすべてつながっているので、つながっているかどうかは判断していないそうです.
図面を建てるときは、重いエッジがあることに注意してください.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#define LL long long
#define _LL __int64
using namespace std;

//const int INF = 0x3f3f3f3f;

int map[55][55];
int deg[55];
stack < pair<int,int> > st;

void dfs(int u)
{
	for(int i = 1; i <= 50; i++)
	{
		if(map[u][i])
		{
			map[u][i]--;
			map[i][u]--;
			dfs(i);
			//printf("%d %d
",i,u); //     ，        
			st.push(make_pair(u,i));//            
		}
	}
}

int main()
{
	int test;
	int n,u,v;
	int flag,start;
	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		memset(map,0,sizeof(map));
		memset(deg,0,sizeof(deg));
		while(!st.empty()) st.pop();

		flag = 1;

		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
		{
			scanf("%d %d",&u,&v);
			map[u][v]++;
			map[v][u]++;
			deg[u]++;
			deg[v]++;
		}

		int maxdeg = -1;
		for(int i = 1; i <= 50; i++)
		{
			if(deg[i]&1)
			{
				flag = 0;
				break;
			}
			else
			{
				if(maxdeg < deg[i])
				{
					maxdeg = deg[i];
					start = i;
				}
			}
		}
		if(item != 1)
			printf("
");
		printf("Case #%d
",item);

		if(!flag)
			printf("some beads may be lost
");
		else
		{
			dfs(start);
			while(!st.empty())
			{
				pair<int,int> u = st.top();
				st.pop();
				printf("%d %d
",u.first,u.second);
			}
		}
	}
	return 0;
}