tarjan求强连通

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define _ 0
 4 const int maxn = 2e5+5;
 5 vector<int>E[maxn];
 6 int dfn[maxn],low[maxn],tot,n,m,vis[maxn],ans=maxn;
 7 stack<int>s;
 8 void tarjan(int x){
 9     low[x]=dfn[x]=++tot;
10     s.push(x);vis[x]=1;
11     for(int i=0;i<E[x].size();i++){
12         int v=E[x][i];
13         if(!dfn[v]){
14             tarjan(v);
15             low[x]=min(low[x],low[v]);
16         }
17         else if(vis[v]){
18             low[x]=min(low[x],dfn[v]);
19         }
20     }
21     if(low[x]==dfn[x]){
22         int sz = 0;
23         while(1){
24             int now = s.top();
25             s.pop(); vis[now]=0;
26             sz++;
27             if(now == x) break;
28         }
29         if(x==1)printf("%d\n",sz);
30     }
31 }
32 int main(){
33     scanf("%d%d", &n, &m);
34     for(int i=1; i<=m; i++){
35         int u,v;
36         scanf("%d%d",&u,&v);
37         E[u].push_back(v);
38     }
39     tarjan(1);
40     return (0^_^0);
41 }