3472518_re.java

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

import java.util.*;

public class Main {

	private Scanner in;
	private int n, m;
	private int [][] LCA = new int [901][901];
	private int [][] tree = new int [901][];
	private final boolean WHITE = false;
	private final boolean BLACK = true;
	private boolean [] color = new boolean [901];
	private int [] ancestor = new int [901];
	private int [] p = new int [901];
	private int [] rank = new int [901];
	private boolean [] isRoot = new boolean [901];
	private int [] count = new int [901];

	public static void main(String [] args) {
		new Main().run();
	}

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

		while (in.hasNext()) {
			n = in.nextInt();
			for (int i = 0; i < n; i++) {
				color[i] = WHITE;
				isRoot[i] = true;
				count[i] = 0;
			}
			for (int i = 0; i < n; i++) {
				str = in.next();
				int index = str.indexOf(':');
				u = Integer.parseInt(str.substring(0, index)) - 1;
				int cnt = Integer.parseInt(str.substring(index + 2, str.length() - 1));
				tree[u] = new int [cnt];
				for (int j = 0; j < cnt; j++) {
					isRoot[tree[u][j] = in.nextInt() - 1] = false;
				}
			}
			for (int i = 0; i < n; i++) {
				if (isRoot[i]) {
					LCA(i);
					break;
				}
			}
			m = in.nextInt();
			for (int i = 0; i < m; i++) {
				String a, b;
				a = in.next();
				b = in.next();
				a = a.substring(1);
				b = b.substring(0, b.length() - 1);
				count[LCA[Integer.parseInt(a) - 1][Integer.parseInt(b) - 1]]++;
			}
			for (int i = 0; i < n; i++) {
				if (count[i] != 0) {
					System.out.println((i + 1) + ":" + count[i]);
				}
			}
		}
	}

	private int findSet(int x) {
		if (x != p[x]) {
			return p[x] = findSet(p[x]);
		} else {
			return x;
		}
	}

	private void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}

	private void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = x;
		} else {
			p[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	private void union(int x, int y) {
		link(findSet(x), findSet(y));
	}

	private void LCA(int u) {

		makeSet(u);
		ancestor[findSet(u)] = u;
		for (int i = 0; i < tree[u].length; i++) {
			int v = tree[u][i];
			LCA(v);
			union(u, v);
			ancestor[findSet(u)] = u;
		}
		color[u] = BLACK;
		for (int i = 0; i < n; i++) {
			if (color[i] == BLACK) {
				LCA[u][i] = LCA[i][u] = ancestor[findSet(i)];
			}
		}
	}
}