csp 201509_4 高速公路

摘要:

tarjan算法

问题描述

某国有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

评测用例规模与约定

前30%的评测用例满足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000;

前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000;

所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。

思路

一开始我用的方法是BFS,把每个节点的可达性信息统计出来,然后再去找他们中间彼此均可达的节点对。这种方法虽然可以得到正确结果,但是内存会爆。上网查了之后发现还是要用tarjan算法,找出图中的强连通分量。u1s1算法原理只懂了个大概,tarjan算法是基于DFS算法的,会给每个访问的节点一个时间戳,时间戳存在DFN[]数组里面,同时还要记录每个节点的能回溯到的最早访问的节点的时间戳,这些存在low[]数组中。当访问到某一个节点i,有DFN[i] == low[i]时,便找到了一个新的强连通分量。

tarjan算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define M 5010//题目中可能的最大点数
int STACK[M],top=0;//Tarjan算法中的栈
bool InStack[M];//检查是否在栈中
int DFN[M] = {0};//深度优先搜索访问次序

int Low[M];//能追溯到的最早的次序
int ComponentNumber=0;//有向图强连通分量个数
int Index=0;//索引号
vector<int> Edge[M];//邻接表表示
vector<int> Component[M];//获得强连通分量结果
int InComponent[M];//记录每个点在第几号强连通分量里
int ComponentDegree[M];//记录每个强连通分量的度

void Tarjan(int i)
{
int j;
DFN[i]=Low[i]=++Index;
InStack[i]=true;STACK[++top]=i;
for (int e=0;e<Edge[i].size();e++)
{
j=Edge[i][e];
if (DFN[j]==0)
{
Tarjan(j);
Low[i]=min(Low[i],Low[j]);
}
else
if (InStack[j]) Low[i]=min(Low[i],DFN[j]);//也可Low[i]=min(Low[i],Low[j]);仅限在求强联通分量时

}
if (DFN[i]==Low[i])
{
ComponentNumber++;
do{
j=STACK[top--];
InStack[j]=false;
Component[ComponentNumber].push_back(j);
InComponent[j]=ComponentNumber;
}
while (j!=i);
}
}

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
int dfn[10005],low[10005];
bool vis[10005],ins[10005];
vector<int>E[10005];
int sum,tot;
stack<int>s;
void tarjan(int v)
{
dfn[v]=low[v]=++tot;
s.push(v);
ins[v]=1;
vis[v]=1;
for(int i=0;i<E[v].size();i++)
{
int vv=E[v][i];
if(!dfn[vv]){
tarjan(vv);
low[v]=min(low[v],low[vv]);
}
else if(ins[vv])
{
low[v]=min(low[v],dfn[vv]);
}
}
if(dfn[v]==low[v])
{
int cnt=0;
while(1)
{
int now=s.top();
s.pop();
ins[now]=0;
vis[v]=0;
cnt++;
if(now==v)break;
}
if(cnt>1){
sum+=cnt*(cnt-1)/2;
}
}
}
int main()
{
//memset(ins,0,sizeof(ins));
//memset(vis,0,sizeof(vis));
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
E[a].push_back(b);
}
sum=0,tot=0;
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i);
}
cout<<sum<<endl;
return 0;
}

参考资料

https://blog.csdn.net/qq_40400202/article/details/80933131

https://baike.baidu.com/item/Tarjan算法/10687825