10248.cpp

ACM 10248 The Integer All-time Champ

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

#define node 10
/*The Integer All-time Champ   */
int map[node][node];
int indegree[node];
int outdegree[node];
char path[300];
int nums;

void find_path(int n)
{
	int i;
	int find;
	path[nums++] = n + '0';
	find = 0;
	for(i = 0 ; i < node ; i++)
		if(map[n][i] > 0 && outdegree[i] > 0)
		{
			indegree[i]--;
			outdegree[n]--;
			map[n][i]--;
			find_path(i);
			find = 1;
			break;
		}
	
	if(find == 0)
		for(i = 0 ; i < node ; i++)
			if(map[n][i] > 0)
			{
				indegree[i]--;
				outdegree[n]--;
				map[n][i]--;
				find_path(i);
				break;
			}
}

void Euler_path()
{
	int i;
	int s;

	while(1)
	{
		s = -1;
		for(i = 0 ; i < node ; i++)
			if(outdegree[i] > indegree[i])
			{
				s = i;
				break;
			}
		if(s == -1)
			for(i = 0 ; i < node ; i++)
				if(outdegree[i] > 0)
				{
					s = i;
					break;
				}
		if(s == -1)
			break;

		find_path(s);
	}
}
int main()
{
	int n, m;
	int i;
	int a, b;

	while(scanf("%d%d", &n, &m) == 2)
	{
		nums = 0;
		if(n < 10)
		{
			if(m < 10)
				for(i = n ; i <= m ; i++)
					path[nums++] = i + '0';
			else if(m < 20)
				for(i = 9 ; i > 1 && i >= n && i > m - 10 ; i--)
					path[nums++] = i + '0';
		}

		if(m > 9)
		{
			memset(map, 0, sizeof(map));
			memset(indegree, 0, sizeof(indegree));
			memset(outdegree, 0, sizeof(outdegree));
			if(n < 10)
				n = 10;
			for(i = n ; i <= m ; i++)
			{
				a = i / 10;
				b = i % 10;
				map[a][b]++;
				indegree[b]++;
				outdegree[a]++;
			}
			Euler_path();
		}
		
		path[nums] = '\0';
		puts(path);
	}
	return 0;
}