问题描述
试题编号： 201509-4
试题名称： 高速公路
时间限制： 1.0s
内存限制： 256.0MB
问题描述：
某国有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 算法求出每一个强联通分量，然后根据题意计算求解。详情见代码注释！（tarjan 算法原理自行查阅，不难理解）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
方法：本质是求强连通分量，可以使用tarjan算法求出每一个强连通分量，之后再计算“便利城市对”
tarjan算法：遍历每一个没有遍历过的节点，设置dfn和low数组分别记录遍历的时间点和最近父节点。
之后遍历它能够到达的节点，并更新low数组；或当到达节点在栈中时直接更新low数组
最后，若当前点low和dfn一样，表示没有其他点与其是强联通分量了，接着找出之前的所有强联通分量点
*
*/
public class csp_2015_09_4 {
static int ans = 0;
static int time = 1;
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
List<Integer>[] map = new ArrayList[n + 5];
for (int i = 0; i <= n; i ++) {
map[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i ++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
map[u].add(v);
}
tarjan(map, n);
System.out.println(ans);
}
private static void tarjan(List<Integer>[] map, int n) {
int[] dfn = new int[n + 5]; // 记录遍历的时间点
int[] low = new int[n + 5]; // 记录最近可返回的父节点
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= n; i ++) {
if (dfn[i] == 0) { // 没有被遍历时
tarjanDfs(i, dfn, low, n, stack, map);
}
}
}
private static void tarjanDfs(int x, int[] dfn, int[] low, int n,
Stack<Integer> stack, List<Integer>[] map) {
dfn[x] = low[x] = time ++;
stack.push(x);
int num = map[x].size();
for (int i = 0; i < num; i ++) { // 遍历x可达的所有节点
int y = map[x].get(i);
if (dfn[y] == 0) { // 没有被遍历时
tarjanDfs(y, dfn, low, n, stack, map);
low[x] = Math.min(low[x], low[y]);
} else if (stack.contains(y)) { // 当y在栈中时
low[x] = Math.min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) { // 若一样，表示自己本身就是一个强连通分量（可能包含其他节点一起）
int k;
int sum = 0;
do {
k = stack.pop();
sum ++;
} while (k != x); // 找到跟x同一个强连通分量
ans += (sum * (sum - 1) / 2);
}
}
}
更多CCF题目代码可参考：https://github.com/dhwgithub/CCF-CSP-Recording
