高速公路_强连通

时间:2021-09-12 03:54:00

问题描述

  某国有n个城市,为了使得城市间的交通更便利,该国国王打算在城市之间修一些高速公路,由于经费限制,国王打算第一阶段先在部分城市之间修一些单向的高速公路。
  现在,大臣们帮国王拟了一个修高速公路的计划。看了计划后,国王发现,有些城市之间可以通过高速公路直接(不经过其他城市)或间接(经过一个或多个其他城市)到达,而有的却不能。如果城市A可以通过高速公路到达城市B,而且城市B也可以通过高速公路到达城市A,则这两个城市被称为便利城市对。
  国王想知道,在大臣们给他的计划中,有多少个便利城市对。

输入格式

  输入的第一行包含两个整数n, m,分别表示城市和单向高速公路的数量。
  接下来m行,每行两个整数a, b,表示城市a有一条单向的高速公路连向城市b。

输出格式

  输出一行,包含一个整数,表示便利城市对的数量。

样例输入

5 5
1 2
2 3
3 4
4 2
3 5

样例输出

3

 1 #include <iostream>
 2 #include <string>
 3 #include <stack>
 4 #include <vector>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 const int N=10005;          
10 int DFN[N]={0};
11 int LOW[N]={0};
12 int time;       
13 stack<int> s;  
14 vector<int> G[N];
15 int vis[N]={0};
16 int instack[N]={0};
17 int result;
18 
19 void tarjan(int u){
20     DFN[u]=LOW[u]=++time; //time从1开始
21     s.push(u);
22     instack[u]=1;
23     vis[u]=1;
24     for(int j=0;j<G[u].size();j++){
25         int v=G[u][j];
26         if(vis[v]==0){
27             tarjan(v);
28             LOW[u]=min(LOW[u],LOW[v]);
29         }
30         else if(instack[v]){
31             LOW[u]=min(LOW[u],DFN[v]);
32         }
33     }
34     int m;
35     int cnt=0; //连通分量内部的节点数
36     if(DFN[u]==LOW[u]){
37         do{
38             m=s.top();
39             instack[m]=0;
40             s.pop();
41             cnt++;
42         }
43         while(m!=u);
44         if(cnt>1){
45             result+=cnt*(cnt-1)/2; //考虑多个连通分量的情况
46         }
47     }
48 }
49 int main(){
50     int n,m; 
51     cin>>n>>m;
52     result=0;
53     time=0;
54 
55     for(int i=0;i<m;i++){
56         int a,b;
57         cin>>a>>b;
58         G[a].push_back(b);
59     }
60 
61     for(int i=1;i<=n;i++){
62         if(vis[i]==0){
63             vis[i]=1;
64             tarjan(i);
65         }
66     }
67     cout<<result;
68     return 0;
69 }