tarjan算法模版

 1 #include<iostream>
 2 #define num 5000
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int n,m;
 7 int f[num];
 8 
 9 
10 typedef struct{
11         int u,v,next;
12         }z;z edg[num];
13 int edgs=0,head[10000];
14 void Addedg(int a,int b){
15      edgs++;
16      edg[edgs].u=a;edg[edgs].v=b;
17      edg[edgs].next=head[a];
18      head[a]=edgs;
19      }
20 
21 void Init(){
22      cin>>n>>m;
23      for(int i=1;i<=n;++i)
24      f[i]=i;
25      
26      memset(head,-1,sizeof(head));
27      for(int i=1;i<=m;++i)
28      {
29        int a,b;
30        cin>>a>>b;
31        Addedg(i,b);
32              }
33      }
34 
35 bool mark[10000],vis[10000];
36 int cordnode[100000],top=-1,times=0;
37 int mintime[100000];
38 void Dfs(int k){
39      int now;
40      now=mintime[k]=times++;
41      vis[k]=1;
42      cordnode[++top]=k;
43      
44      for(int i=head[k];i!=-1;i=edg[i].next)
45      {
46        int v=edg[i].v;
47        if(mark[v]) continue;
48        if(!vis[v]) Dfs(v);
49        if(mintime[k]>mintime[v]) 
50        mintime[k]=mintime[v]; 
51              }
52      
53      if(mintime[k]==now)
54      {
55        while(cordnode[top]!=k)
56        {
57          f[cordnode[top]]=k;
58          mark[cordnode[top]]=1;
59          top--;               
60                               } 
61        f[cordnode[top]]=k;
62        top--; 
63                         }
64      
65      
66      }
67 
68 int main()
69 {
70     Init();
71     
72     for(int i=1;i<=n;++i)
73     if(!mark[i]) Dfs(i);
74     
75     int p[10000]={0};
76     
77     for(int i=1;i<=n;++i)
78     p[f[i]]=1;
79     int ans=0;
80     for(int i=1;i<=n;++i)
81     if(p[i]) ans++;
82     cout<<ans<<endl;
83     system("pause");
84     
85     }