题意：求强联通分量

Tarjan算法

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<memory.h>
 5 #include<string.h>
 6 #include<algorithm>
 7 #include<cmath>
 8 #include<map>
 9 #define clc(a,b) memset(a,b,sizeof(a))
10 typedef long double ld;
11 typedef long long ll;
12 const int N = 30;
13 const double eps=1e-9;
14 const int inf=-100000;
15 const int maxn=1e5+10;
16 const int num=10001;
17 const double Pi=acos(-1);
18 using namespace std;
19 
20 struct gragh
21 {
22     int to;
23     int next;
24 } V[num];
25 
26 bool instack[num]= {false};
27 int low[num]= {0},DFN[num]= {0},Stap[num]= {0},Belong[num]= {0};
28 int answer=0;
29 int Dindex,stop,Bcnt;
30 int head[num];
31 int edge;
32 
33 void add(int a,int b)
34 {
35     V[edge].to=b;
36     V[edge].next=head[a];
37     head[a]=edge++;
38 
39 }
40 void tarjan(int u)
41 {
42     int v;
43     DFN[u]=low[u]=++Dindex;
44     instack[u]=true;
45     Stap[stop++]=u;
46     for(int i=head[u]; i!=-1; i=V[i].next)
47     {
48         v=V[i].to;
49         if(!DFN[v])
50         {
51             tarjan(v);
52             if(low[v]<low[u])
53                 low[u]=low[v];
54         }
55         else if(instack[v]&&DFN[v]<low[u])
56             low[u]=DFN[v];
57     }
58     if(DFN[u]==low[u])
59     {
60         int sum=0;
61         Bcnt++;
62         do
63         {
64             v=Stap[--stop];
65             instack[v]=false;
66             Belong[v]=Bcnt;
67             sum++;
68         }
69         while(v!=u);
70         cout<<sum<<endl;
71         if(sum!=0)
72             answer+=(sum*(sum-1))/2;
73     }
74 }
75 void solve(int N)
76 {
77     stop=Bcnt=Dindex=0;
78     // clc(DFN,0);
79     for(int i=1; i<=N; i++)
80         if(!DFN[i])
81             tarjan(i);
82 }
83 
84 int main()
85 {
86     int n,m;
87     int a,b;
88     cin>>n>>m;
89     clc(head,-1);
90     edge=0;
91     for(int i=0; i<m; i++)
92     {
93         cin>>a>>b;
94         add(a,b);
95     }
96     solve(n);
97     cout<<answer<<endl;
98     return 0;
99 }

View Code

 

版权声明：本文为ITUPC原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ITUPC/p/5059877.html