CCF试题：高速公路（Targin）

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++;
	}
}