竞赛图tarjan缩点后得到的拓扑图一定是一条链

因为竞赛图任意两点的前后顺序确定，只有一种拓扑序列

 

竞赛图tarjan缩完点后，若出现强联通分量A和B

那么A中所有点 和 B中所有点的连边 要么全指向A中所有点，要么全指向B中所有点

否则A和B就是一个强联通分量

所以把缩完点之后按点的入度从小到大排序，即可得到竞赛图的拓扑序列

 

在这个拓扑序列上，可以从前面的强联通分量中任意一个点出来，到达后面的强联通分量的任意一个点

因为竞赛图的任意强联通子图存在一条哈密顿回路

 

那么再求出每个强联通分量的哈密顿回路

枚举起点，先把起点所在的哈密顿回路扔进栈，然后再按拓扑序把后面的哈密顿回路扔进栈，输出即可

 

如何在竞赛图哈密顿路径的基础上构造回路，详请参见博客

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 2001int n;bool mp[N][N];int tot;int dfn[N],low[N];int st[N],top;bool vis[N];int cnt;int id[N];vector
         
          scc[N];int nxt[N];int pos[N],in[N];template
          
           void read(T &x){ x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void tarjan(int x){ dfn[x]=low[x]=++tot; st[++top]=x; vis[x]=true; for(int i=1;i<=n;++i) { if(!mp[x][i]) continue; if(!dfn[i]) { tarjan(i); low[x]=min(low[x],low[i]); } else if(vis[i]) low[x]=min(low[x],dfn[i]); } if(low[x]==dfn[x]) { cnt++; while(st[top]!=x) { scc[cnt].push_back(st[top]); id[st[top]]=cnt; vis[st[top--]]=false; } scc[cnt].push_back(x); id[x]=cnt; vis[x]=false; top--; }}bool cmp(int a,int b){ return in[a]
           
            in[id[i]]) insert(scc[t][0]); printf("%d ",top); for(int j=1;j<=top;++j) { printf("%d",st[j]); putchar(j==top ? '\n' : ' '); } }}