SGU 122.The book （哈密顿回路）

题目描述

有一群人从1到N标号，而且这群人中每个人的朋友个数不少于 (N+1)/2 个。

编号为1的人有一本其他人都想阅读的书。

写一个程序，找到一种传阅顺序使得书本只经过每个人手中一次，并且一个人只能将书本传给他的朋友，并且书本最后必须传回给第一个人。（注释：如果A是B的朋友，那么B一定是A的朋友）

输入

第一行包含一个数字N。

接下来的有N行，第i行表示第i-1个人的朋友

输出

如果不存在解决方案，则输出 'No solution' 。否则你将输出1行包含N+1个整数，表示传阅路径，由1开始、由1结尾。

输入样例

4

2 3

1 4

1 4

2 3

输出样例

1 3 4 2 1

---

Solution:

每个人至少有（n+1）/2 个朋友,一定存在哈密顿回路.

找到哈密顿路后,从1 的位置开始输出,最后再输出一个1.

code:

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define INF 1111

using namespace std;

bool edge[INF][INF];

int ans[INF], vis[INF];

int n, tol = 2, t, s = 1;

void expand() {

	int i;

	while (1) {

		for (i = 1; i <= n; i++) {

			if (edge[t][i] && !vis[i]) {

				ans[tol++] = i;

				t = i, vis[i] = 1;

				break;

			}

		}

		if (i > n) return;

	}

}

void Hamiton() {

	int i, j;

	for (i = 1; i <= n; i++) if (edge[s][i]) break;

	t = i;

	ans[0] = s, ans[1] = t;

	vis[s] = vis[t] = 1;

	while (1) {

		expand();

		reverse (ans, ans + tol);

		swap (s, t);

		expand();

		if (!edge[s][t]) {

			for (i = 1; i < tol - 2; i++)

				if (edge[ans[i]][t] && edge[ans[i + 1]][s]) break;

			reverse (ans + i + 1, ans + tol);

			t = ans[tol - 1];

		}

		if (tol == n) return;

		for (j = 1; j <= n; j++) {

			if (vis[j]) continue;

			for (i = 1; i < tol - 1; i++)

				if (edge[ans[i]][j])	break;

			if (edge[ans[i]][j]) break;

		}

		s = ans[i - 1], t = j;

		reverse (ans, ans + i);

		reverse (ans + i, ans + tol);

		ans[tol++] = j, vis[j] = 1;

	}

}

int main() {

	char ci;

	scanf ("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf ("%d", &t);

		edge[i][t] = edge[t][i] = 1;

		ci = getchar();

		while (ci != '\n' && ci != '\r' && ci != EOF)

			scanf ("%d", &t), edge[i][t] = edge[t][i] = 1, ci = getchar();

	}

	Hamiton();

	int i;

	for (i = 0; i < n; i++)

		if (ans[i] == 1) break;

	for (int j = 0; j < n; j++) {

		printf ("%d ", ans[i]);

		i++;

		if (i == n) i = 0;

	}

	putchar ('0' + 1);

	return 0;

}