150904 高速公路 ccf

 1 /*
 2 dfn为访问序号（时间戳）
 3 low为当前节点及其子树中结点最小的访问序号，相似并查集
 4 */
 5 void tarjan(int u){
 6 
 7 　　DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
 8 
 9 　　Stack.push(u)   // 将节点u压入栈中
10 
11 　　for each (u, v) in E // 枚举每一条边
12     {
13             if (v is not visted) // 若是节点v未被访问过
14 
15 　　　　{
16                 tarjan(v) // 继续向下找
17                 Low[u] = min(Low[u], Low[v])
18             }　　　　
19 
20 　　　　else if (v in S) // 若是节点u还在栈内
21 
22 　　　　{   Low[u] = min(Low[u], DFN[v])   }
23     }
24 
25 　　if (DFN[u] == Low[u]) // 若是节点u是强连通份量的根
26    {
27            repeat 
28        
29            v = S.pop  // 将v退栈，为该强连通份量中一个顶点
30 
31     　　 print v
32 
33 　　     until (u== v)    
34    }
35 
36 }                    

 1 //Kosaraju
 2 #include<bits/stdc++.h>
 3 
 4 using namespace std;
 5 
 6 #define MAXN 10005
 7 
 8 vector<int> Map1[MAXN];
 9 vector<int> Map2[MAXN];
10 stack<int> sta; 
11 int vis[MAXN];
12 long long int ans=0,num=0;
13 int n,m;
14 
15 int size,v;
16 void dfs2(int s){
17     
18     for(int i=0;i<Map2[s].size();i++){
19         v=Map2[s][i];
20         if(vis[v]==0){
21             vis[v]=1;
22             dfs2(v);    
23         }
24     }
25     sta.push(s);
26 }
27 
28 void dfs1(int s){
29     for(int i=0;i<Map1[s].size();i++){
30         v=Map1[s][i];
31         if(vis[v]==0){
32             //cout<<v<<' ';
33             vis[v]=1;
34             num++;
35             dfs1(v);
36         }
37     }
38 }
39 
40 long long int C(int x){
41     if(x<=1){
42         return 0;
43     }
44     else{
45         long long int a=1;
46         for(int i=x;i>x-2;i--){
47             a*=i;
48         }
49         return a/2;
50     }
51 }
52 
53 int main(){
54     cin>>n>>m;
55     int a,b;
56     for(int i=0;i<m;i++){
57         cin>>a>>b;
58         Map1[a].push_back(b);
59         Map2[b].push_back(a);
60     }
61     
62     memset(vis,0,sizeof(vis));
63     for(int i=0;i<=n;i++){
64         if(vis[i]==0){
65             vis[i]=1;
66             dfs2(i);
67         }
68     }
69     
70     memset(vis,0,sizeof(vis));
71     int v;
72     while(!sta.empty()){
73         v=sta.top();
74         sta.pop();
75         
76         if(vis[v]==0){
77             //cout<<v<<' ';
78             vis[v]=1;
79             num=1;
80             dfs1(v);
81             //cout<<num<<endl;
82             ans+=C(num);
83         }
84     }
85 
86     cout<<ans;
87     
88     return 0;
89 }

 1 //tarjan
 2 
 3 #include<bits/stdc++.h>
 4 
 5 using namespace std;
 6 
 7 #define MAXN 10005
 8 
 9 vector<int> Map[MAXN];
10 stack<int> sta;
11 int vis[MAXN];
12 int dfn[MAXN];
13 int low[MAXN];
14 int insta[MAXN];
15 long long int num=0,ans=0;
16 int n,m,index;
17 
18 long long int C(int x){
19     if(x<=1){
20         return 0;
21     }
22     else{
23         long long int a=1;
24         for(int i=x;i>x-2;i--){
25             a*=i;
26         }
27         return a/2;
28     }
29 }
30 
31 void tarjan(int u)
32 {
33     index++;
34     dfn[u]=low[u]=index;
35     vis[u]=1;
36     sta.push(u);
37     insta[u]=1;
38     int  size=Map[u].size();
39     for(int i=0;i<size;i++){
40         int v=Map[u][i];
41         if(vis[v]==0){
42             tarjan(v);
43             low[u]=min(low[u],low[v]);
44         }
45         else if(insta[v]==1){
46             low[u]=min(low[u],dfn[v]);
47         }
48     }
49     num=0;
50     if(dfn[u]==low[u]){
51         int v;
52         do{
53             v=sta.top();
54             //cout<<v<<' ';
55             sta.pop();
56             insta[v]=0;
57             num++;
58         }while(v!=u);
59         //cout<<endl;
60     }
61     ans+=C(num);
62 }
63 
64 int main(){
65     cin>>n>>m;
66     int a,b;
67     for(int i=0;i<m;i++){
68         cin>>a>>b;
69         Map[a].push_back(b);
70     }
71     memset(vis,0,sizeof(vis));
72     memset(insta,0,sizeof(insta));
73     index=0;
74     for(int i=1;i<=n;i++){
75         if(vis[i]==0){            
76             tarjan(i);
77         }
78     }
79     cout<<ans;
80     
81     return 0;
82 }