问题描述
某国有n个城市，为了使得城市间的交通更便利，该国国王打算在城市之间修一些高速公路，由于经费限制，国王打算第一阶段先在部分城市之间修一些单向的高速公路。
现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。
国王想知道，在大臣们给他的计划中，有多少个便利城市对。
现在，大臣们帮国王拟了一个修高速公路的计划。看了计划后，国王发现，有些城市之间可以通过高速公路直接（不经过其他城市）或间接（经过一个或多个其他城市）到达，而有的却不能。如果城市A可以通过高速公路到达城市B，而且城市B也可以通过高速公路到达城市A，则这两个城市被称为便利城市对。
国王想知道，在大臣们给他的计划中，有多少个便利城市对。
输入格式
输入的第一行包含两个整数n, m，分别表示城市和单向高速公路的数量。
接下来m行，每行两个整数a, b，表示城市a有一条单向的高速公路连向城市b。
接下来m行，每行两个整数a, b，表示城市a有一条单向的高速公路连向城市b。
输出格式
输出一行，包含一个整数，表示便利城市对的数量。
样例输入
5 5
1 2
2 3
3 4
4 2
3 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。
前60%的评测用例满足1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000；
所有评测用例满足1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000。
在CCF的平台上无限编译错误，，我不知道为什么。。。
import java.util.Scanner;
public class Main {
static class Edge { // 邻接表
int v;
int next;
}
static int[] first;// first[]头结点数组
static int tot;
static int n, m; // 节点数，边数
static Edge[] edge; // 边
static int []Stack;
static int top;
static boolean[] inStack;
static int[] DFN; // DFN[]为深搜次序数组(标记时间)
static int[] low; // Low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号
static int Count, cnt; // Count记录强连通分量
static int[] Belong;// Belong[]为每个结点所对应的强连通分量标号数组
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
tot = 0;
Count = 0;
cnt = 0;
Stack = new int[n+1];
top=0;
edge = new Edge[m + 1];
first = new int[n + 1];
for (int i = 1; i <= n; i++) {
first[i] = -1;
}
Belong = new int[n + 1];
DFN = new int[n + 1];
low = new int[n + 1];
inStack = new boolean[n + 1];
int u, v;
for (int i = 0; i < m; i++) {
u = sc.nextInt();
v = sc.nextInt();
addEdge(u, v);
}
cnt = 0;
int[] hash = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (DFN[i] == 0) {
Targin(i);
}
}
for (int i = 1; i <= n; i++) {
hash[Belong[i]]++;
}
int sum = 0;
for (int i = 1; i <= Count; i++) {
if (hash[i] != 1) {
sum = sum + hash[i] * (hash[i] - 1) / 2; // 除以2的原因是2-3 和 3-2是一条
}
}
System.out.println(sum);
}
private static void Targin(int u) {
DFN[u] = low[u] = ++cnt;
inStack[u] = true;
Stack[top++]=u;
// 枚举边
for (int e = first[u]; e != -1; e = edge[e].next) {
int v = edge[e].v;
if (DFN[v] == 0) { // j没被访问过
Targin(v);
// 更新结点u所能到达的最小次数层
if (low[u] > low[v])
low[u] = low[v];
} else if (inStack[v] && low[u] > DFN[v]) {// 如果v结点在栈内
low[u] = DFN[v];
}
}
if (DFN[u] == low[u]) {
// 如果节点u是强连通分量的根
Count++;
int v;
do {
v = Stack[--top];
Belong[v] = Count;
inStack[v] = false;
} while (u != v);
}
}
private static void addEdge(int u, int v) { // 构建邻接表
edge[tot] = new Edge();
edge[tot].v = v;
edge[tot].next = first[u];
first[u] = tot++;
}
}