CCF试题：高速公路（Targin）

问题描述

　　某国有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个便利城市对，它们分别是(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。

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

	}

}

巴特西

CCF试题：高速公路（Targin）

最新文章

热门文章