题解 P1718 【图形复原】

· · 题解

神奇的深搜！！

然而居然有人用tarjan写

大致思路

使用f[i][j]表示i到j的距离，ans[i]表示答案的第i个数是多少,used[i]表示i这个点是否被用过

dfs时，如果再次搜索到1并且答案长度变成了n+1,说明找到答案（因为字典序最小），输出后直接退出程序；否则，扩展这个点

dfs(nownow,anscnt):nownow表示当前的点，anscnt表示标记了多少个点。

详见注释。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
bool f[51][51],used[2500];
int ans[2500];
void dfs(int nownow,int anscnt)
{
    if(nownow==1&&anscnt==n+1)
    {
        for(int i=1;i<anscnt;i++) printf("%d ",ans[i]);
        exit(0);//输出答案，直接退出
    }
    for(int i=1;i<=n;i++)
        if(i!=nownow&&f[nownow][i]&&(!used[i]||(i==1&&anscnt==n)))//这不是当前的点，并且联通、而且没有用过或者这是1并且搜索完了
        {
            used[i]=1;ans[anscnt+1]=i;//标记为使用过，记录
            dfs(i,anscnt+1);
            used[i]=0;//回溯，重新标记为没有用过
        }
}
int main()
{
    scanf("%d",&n);
    while(scanf("%d %d",&a,&b)!=EOF)
    {
        f[a][b]=f[b][a]=1;//双向的
    }
    ans[1]=1;used[1]=1;//1这个点已经用过了，标记一下
    dfs(1,1);
    return 0;
}