这题点的个数(<=50)有限,所以直接暴力。。
#include <iostream> #include <cstdio> #include <cstring> #define N 102 using namespace std; int T,n,cnt; int dis[N][N],vis[N]; int pm[N]; void init() { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(pm,0,sizeof(pm)); cnt=0; } int dfs(int a) { int i,k=0; if(cnt>=n)return 1; for(i=1; i<=n; i++) if(!vis[i]&&dis[a][i]) { vis[i]=1; pm[cnt++]=i; if(dfs(i)==1){k=1;break;} vis[i]=0;//DFS的精髓——还原 cnt--; } return k; } int main() { int i,a,b; scanf("%d",&T); while(T--) { init(); scanf("%d",&n); for(i=0; i<n*(n-1)/2; i++) { scanf("%d%d",&a,&b); dis[a][b]=1; } for(i=1; i<=n; i++) { vis[i]=1; pm[cnt++]=i; if(dfs(i)) { for(i=0; i<n-1; i++)printf("%d ",pm[i]); printf("%d\n",pm[i]); break; } vis[i]=0; cnt--; } } return 0; }