CCF考试——201509-4高速公路
概要
问题描述
某国有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
样例说明
城市间的连接如图所示。有3个便利城市对，它们分别是(2, 3), (2, 4), (3, 4)，请注意(2, 3)和(3, 2)看成同一个便利城市对。
评测用例规模与约定
前30%的评测用例满足1 ≤ n ≤ 100, 1 ≤ m ≤ 1000； 前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000； 所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。
思路
这道题主要是找有向图强联通分量的个数，算法应用的是Tarjan算法。首先定义两个数组：dfn与low。dfn数组是用来标记dfs过程中第几个遍历到的点。low数组定义如下： low[u] = min(low[u],low[v]),u代表当前结点，v代表其能到达的结点。这个数组在刚刚到达节点u的时候初始化：low[u]=dfn[u]。然后在进行下一层深搜之后回溯回来的时候，维护low[u]。如果我们发现了某个节点回溯之后的low[u]值还是==dfn[u]的值，那么这个节点无疑就是一个关键节点：从这个节点能够到达其强连通分量中的其他节点，但是没有其他属于这个强连通分量以外的点能够到达这个点，所以这个点的low[u]值维护完了之后还是和dfn[u]的值一样。
代码（80分）
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int dfn[10001];
int low[10001];
int in_stack[10001];
vector<int> g[10001];
stack<int> Stack;
int isvisited[10001];
int n,m;
int a,b;
int time = 0;
int ans;
void tarjan(int v)
{
Stack.push(v);
in_stack[v] = 1;
isvisited[v] = 1;
dfn[v] = low[v] = ++time;
for(int i = 0 ; i < g[v].size() ; i++){
int w = g[v][i];
if(isvisited[w] == 0){
tarjan(w);
low[v] = min(low[v],low[w]);
}else if(in_stack[v]){
low[v] = min(low[v],dfn[w]);
}
}
if(low[v] == dfn[v]){
int cnt = 0;
int j = 0;
do{
j = Stack.top();
in_stack[j] = 0;
Stack.pop();
cnt++;
}while(j != v);
ans += cnt*(cnt-1)/2;
}
}
int main()
{
cin>>n>>m;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(in_stack,0,sizeof(in_stack));
memset(isvisited,0,sizeof(isvisited));
memset(g,0,sizeof(g));
for(int i = 0 ; i < m ; i++){
cin>>a>>b;
g[a].push_back(b);
}
for(int i = 1 ; i <= n ; i++){
if(isvisited[i] == 0){
tarjan(i);
}
}
cout<<ans<<endl;
return 0;
}