大约是今年4月学的算法了，后来5月的时候做题还写了一个退化的tarjanQAQ。
时间复杂度：O(n+m)
用途：有向图缩环
1 #include<set> 2 #include<cmath> 3 #include<ctime> 4 #include<queue> 5 #include<stack> 6 #include<cstdio> 7 #include<vector> 8 #include<cstring> 9 #include<cstdlib> 10 #include<iostream> 11 #include<algorithm> 12 #define N 10001 13 #define M 100001 14 using namespace std; 15 struct graph{ 16 int nxt,to; 17 }e[M]; 18 int g[N],f[N]/*father*/,dfn[N],low[N],sta[N]/*stack;stack[0]:the top of the stack*/,m,n,cnt; 19 /*dfn[u]:遍历到u点的时间; low[u]:u点可到达的各点中最小的dfn[v],即最高层的点*/ 20 bool ins[N];//in stack 21 inline void addedge(int x,int y){ 22 e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y; 23 } 24 inline void tarjan(int u){ 25 dfn[u]=low[u]=++cnt; 26 sta[++sta[0]]=u;ins[u]=true; 27 for(int i=g[u];i;i=e[i].nxt) 28 if(!dfn[e[i].to]){ 29 tarjan(e[i].to); 30 low[u]=min(low[u],low[e[i].to]); 31 } 32 else if(ins[e[i].to]) 33 low[u]=min(low[u],low[e[i].to]); 34 if(dfn[u]==low[u]){ 35 while(sta[sta[0]+1]!=u){ 36 f[sta[sta[0]]]=u; 37 ins[sta[sta[0]--]]=false; 38 } 39 } 40 } 41 inline void init(){ 42 scanf("%d%d",&n,&m); 43 for(int i=1,j,k;i<=m;i++){ 44 scanf("%d%d",&j,&k); 45 addedge(j,k); 46 } 47 cnt=0; 48 for(int i=1;i<=n;i++) 49 if(!dfn[i]) tarjan(i); 50 for(int i=1;i<=n;i++) 51 printf("%d's father is %d ",i,f[i]); 52 } 53 int main(){ 54 freopen("tarjan.in","r",stdin); 55 freopen("tarjan.out","w",stdout); 56 init(); 57 fclose(stdin); 58 fclose(stdout); 59 return 0; 60 }