time limit per test: 0.25 sec.
memory limit per test: 4096 KB
There is a group of N (2<=N<=1000) people which are numbered 1 through N, and everyone of them has not less than [ (N+1) / 2 ] friends. A man with number 1 has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.

Input

First line of input contains number N. Next N lines contain information about friendships. (i+1)-th line of input contains a list of friends of i-th man.

Output

If there is no solution then your program must output ‘No solution’. Else your program must output exactly N+1 number: this sequence should begin and should come to end by number 1, any two neighbours in it should be friends, and any two elements in it, except for the first and last, should not repeat.

Sample Input

4
2 3
1 4
1 4
2 3

Sample Output

1 3 4 2 1

题意：

编号为1的人的手里有一本书，然后他的朋友会借书来看，借书的人的朋友也会来借这本书，也就是说这本书会通过人脉网络传递下去，现在让你给出一种传递方案，使得每个人都会且只会看一次这本书，并且最后能传回编号为1的人手里。
输入：
首先会给你一个数字n，代表有n个人，然后下面有n行，每行至少(n+1)/2个人，最多有n-1个人，第i行所代表的意思是编号为i的人的朋友是谁。
输出：
将路径输出。

题解：

很显然，每个点必须且只能访问一次，于是问题变成求哈密顿回路！
关于哈密顿回路的详解请看另一篇博文。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1300;
int n, sum = 0;
bool Map[maxn][maxn];
int ans[maxn], vis[maxn];
inline void reverse(int st, int t)
{
    while (st < t)
    {
        swap(ans[st], ans[t]);
        st++;
        t--;
    }
}
void Hamilton()
{
    memset(vis, 0, sizeof(vis));
    int st = 1, t;
    int ans1 = 2;
    int i, j;
    for (i = 1; i <= n; i++)
        if (Map[st][i])
            break;
    t = i;
    vis[st] = vis[t] = 1;
    ans[0] = st;
    ans[1] = t;
    while (1)
    {
        while (1)
        {
            for (i = 1; i <= n; i++)
            {
                if (Map[t][i] && !vis[i])
                {
                    ans[ans1++] = i;
                    vis[i] = 1;
                    t = i;
                    break;
                }
            }
            if (i > n)
                break;
        }
        reverse(0, ans1 - 1);
        swap(st, t);
        while (1)
        {
            for (i = 1; i <= n; i++)
            {
                if (Map[t][i] && !vis[i])
                {
                    ans[ans1++] = i;
                    vis[i] = 1;
                    t = i;
                    break;
                }
            }
            if (i > n)
                break;
        }
        if (!Map[st][t])
        {
            for (i = 1; i < ans1 - 2; i++)
                if (Map[ans[i]][t] && Map[st][ans[i + 1]])
                    break;
            t = ans[++i];
            reverse(i, ans1 - 1);
        }
        if (ans1 == n)
            return;
        for (i = 1; i <= n; i++)
        {
            if (vis[i])
                continue;
            for (j = 1; j < ans1 - 2; j++)
                if (Map[ans[j]][i])
                    break;
            if (Map[ans[j]][i])
                break;
        }
        st = ans[j - 1];
        t = i;
        reverse(0, j - 1);
        reverse(j, ans1 - 1);
        ans[ans1++] = i;
        vis[i] = 1;
    }
}
char s[3 * maxn];
int main()
{
    memset(Map, 0, sizeof(Map));
    cin >> n;
    getchar();
    for (int j = 1; j <= n; j++)
    {
        gets(s);
        int len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            int temp = 0;
            if (s[i] == ' ')
                continue;
            while (i < len && s[i] >= '0' && s[i] <= '9')
                temp = temp * 10 + s[i] - '0', i++;
            Map[j][temp] = Map[temp][j] = 1;
        }
    }
    Hamilton();
    for (int i = 0; i < n; i++)
        if (ans[i] == 1)
        {
            for (int j = i, k = 0; k < n; j = (j + 1) % n, k++)
                printf("%d ", ans[j]);
            printf("1\n");
            break;
        }
    printf("\n");
    return 0;
}