学步园

题目链接：Click here~~

题意：

n 个点的竞赛图，找出它的哈密顿路（n <= 100）。

解题思路：

首先，竞赛图是指每两个点之间都有一条边的有向图（即边数为 n*(n-1)/2 ）。

然后，对于竞赛图，一定存在哈密顿路。转载一个证明：

求竞赛图中的哈密顿路的算法：

首先,由数学归纳法可证竞赛图在n>=2时必存在哈密顿路；

(1)n=2时显然；

(2)假设n=k时,结论成立,哈密顿路为V1,V2,...,Vi,...,Vk；

     现添加第k+1个结点，若存在弧<Vi,Vk+1>和弧<Vk+1,Vi+1>，则可得哈密顿回路V1,V2,...,Vi,Vk+1,Vi+1,...,Vk；

     若不存在上述的vi,考虑到Vk+1与v1~vk的连通状况,则只有下面 3 种原哈密顿路的情况：

     1.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vi,Vk+1>，那么可得哈密顿回路V1,V2,...,Vi,...,Vk,Vk+1；

     2.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vk+1,Vi>，那么可得哈密顿回路Vk+1,V1,V2,...,Vi,...,Vk；

     3.存在一个中间结点m，使得所有的Vi(1<=i<=m)与Vk+1的弧方向为<Vk+1,Vi>,所有的Vj(m<j<=k)与Vk+1的弧的方向为<Vj,Vk+1>，这时依然可以构造哈密顿路 V1,V2,...,Vi,...,Vk,Vk+1；

对于证明，可能一下子想不到为什么能分为这三种情况。可以从 V1 与 Vk+1 及 Vk 与 Vk+1 的四种情况入手。

代码很好写，复杂度O(n^2)。

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

using namespace std;

const int N = 1e2 + 5;

bool reach[N][N];

void Hamitton(int n)
{
    vector<int> ans;
    ans.push_back(1);
    for(int i=2;i<=n;i++)
    {
        bool cont = false;
        for(int j=0;j<(int)ans.size()-1;j++)
            if(reach[ ans[j] ][i] && reach[i][ ans[j+1] ])
            {
                ans.insert(ans.begin()+j+1,i);
                cont = true;
                break;
            }
        if(cont)
            continue;
        if(reach[ ans.back() ][i])
            ans.push_back(i);
        else
            ans.insert(ans.begin(),i);
    }
    for(int i=0;i<n;i++)
        printf("%d%c",ans[i],i==n-1?'\n':' ');
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        memset(reach,false,sizeof(reach));
        scanf("%d",&n);
        if(n == 1)
            puts("1");
        else
        {
            for(int i=0;i<n*(n-1)/2;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                reach[u][v] = true;
            }
            Hamitton(n);
        }
    }
    return 0;
}