1 #include <iostream> 2 3 using namespace std; 4 5 const int MAXN=100010; 6 const int MAXM=100010; 7 8 struct Edge 9 { 10 int to,next,w; 11 }e[MAXM*2]; 12 int head[MAXN]; 13 14 int cnt=0; 15 void addEdge(int x,int y,int z=1) 16 { 17 cnt++; 18 e[cnt].next=head[x]; 19 e[cnt].to=y; 20 e[cnt].w=z; 21 head[x]=cnt; 22 return; 23 } 24 25 int tot=0; //时间 26 int dfn[MAXN],low[MAXN]; //dfn-记录时间戳,low-根 27 int s[MAXN],idx=0; //栈数组,下标 28 bool instack[MAXN]; //是否在栈中 29 void tarjan(int x) //tarjan算法,实际上是一个dfs递归的过程 30 { 31 dfn[x]=low[x]=++tot; //更新时间戳和连通子图的根 32 s[++idx]=x; //进栈 33 instack[x]=true; //标记为在栈中 34 for (int i=head[x];i!=0;i=e[i].next) //遍历每条边的另一端(终点) 35 { 36 int j=e[i].to; //终点 37 if (!dfn[j]) //没访问过 38 { 39 tarjan(j); //继续dfs 40 low[x]=min(low[x],low[j]); //更新根 41 } 42 else if (instack[j]) low[x]=min(low[x],low[j]); //访问过且在栈中,更新根 43 //如果访问过且不在栈中,则说明已经形成一个连通子图 44 } 45 if (dfn[x]==low[x]) //时间戳和根相等,说明是根 46 { 47 do 48 { 49 cout<<s[idx]<<" "; 50 instack[s[idx]]=false; 51 idx--; 52 }while (x!=s[idx+1]); //出栈并输出 53 cout<<endl; 54 } 55 return; 56 } 57 58 int main() 59 { 60 int n,m; 61 cin>>n>>m; 62 int u,v; 63 for (int i=1;i<=m;i++) 64 { 65 cin>>u>>v; 66 addEdge(u,v); 67 } 68 for (int i=1;i<=n;i++) 69 { 70 if (!dfn[i]) tarjan(i); //没有时间戳,说明未访问过,则遍历,防止图没走完 71 } 72 73 return 0; 74 }