3708753_ac_2157ms_5044k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	private Scanner in;
	private int n, m;
	private Edge[] e1;
	private Edge[] e2;
	private int cnt;
	private int[] st1;
	private int[] ed1;
	private int[] st2;
	private int[] ed2;
	private boolean[] visited;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().run();
	}

	class Edge implements Comparable<Edge> {

		int from, to;

		public Edge(int from, int to) {
			this.from = from;
			this.to = to;
		}

		public int compareTo(Edge other) {
			return from - other.from;
		}
	}

	private void dfs1(int u) {
		for (int i = st1[u]; i <= ed1[u]; i++) {
			if (visited[e1[i].to] == false) {
				visited[e1[i].to] = true;
				cnt++;
				dfs1(e1[i].to);
			}
		}
	}

	private void dfs2(int u) {
		for (int i = st2[u]; i <= ed2[u]; i++) {
			if (visited[e2[i].to] == false) {
				visited[e2[i].to] = true;
				cnt++;
				dfs2(e2[i].to);
			}
		}
	}

	private void run() {
		in = new Scanner(System.in);
		int u, v;

		n = in.nextInt();
		m = in.nextInt();
		e1 = new Edge[m];
		e2 = new Edge[m];
		st1 = new int[n + 1];
		ed1 = new int[n + 1];
		st2 = new int[n + 1];
		ed2 = new int[n + 1];
		visited = new boolean[n + 1];
		for (int i = 0; i < m; i++) {
			u = in.nextInt();
			v = in.nextInt();
			e1[i] = new Edge(u, v);
			e2[i] = new Edge(v, u);
		}
		Arrays.sort(e1);
		Arrays.sort(e2);
		Arrays.fill(st1, 0);
		Arrays.fill(st2, 0);
		Arrays.fill(ed1, -1);
		Arrays.fill(ed2, -1);
		for (int i = 0; i < m; i++) {
			ed1[e1[i].from] = i;
			ed2[e2[i].from] = i;
		}
		for (int i = m - 1; i >= 0; i--) {
			st1[e1[i].from] = i;
			st2[e2[i].from] = i;
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			cnt = 1;
			Arrays.fill(visited, false);
			visited[i] = true;
			dfs1(i);
			Arrays.fill(visited, false);
			visited[i] = true;
			dfs2(i);
			if (cnt == n) {
				ans++;
			}
		}
		System.out.println(ans);
	}
}