4263384_tle.java

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

import java.util.*;

public class Main {

	private int t, n;

	private Scanner in;

	private HashMap<String, Integer> hm = new HashMap<String, Integer>();

	private int cnt;

	private int[] isWriter = new int[100000];

	private String[] names = new String[100000];

	private ArrayList[] al = new ArrayList[100];

	private boolean[][] map = new boolean[100][100];

	private Integer[] writers = new Integer[100];

	private TreeSet[] ts = new TreeSet[100];

	private int cas = 1;

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

	private int getId(String name) {
		if (hm.containsKey(name)) {
			return hm.get(name);
		}
		names[cnt] = name;
		hm.put(name, cnt);
		return cnt++;
	}

	private void run() {
		in = new Scanner(System.in);
		String line;

		for (int i = 0; i < 100; i++) {
			al[i] = new ArrayList<Integer>();
			ts[i] = new TreeSet<String>();
		}
		while (true) {
			t = in.nextInt();
			n = in.nextInt();
			if (t == 0 && n == 0) {
				break;
			}
			cnt = 0;
			Arrays.fill(isWriter, 0, t, -1);
			hm.clear();
			in.nextLine();
			for (int i = 0; i < n; i++) {
				line = in.nextLine();
				ts[i].clear();
				Arrays.fill(map[i], false);
				al[i].clear();
				StringTokenizer st = new StringTokenizer(line, " ");
				String writer = st.nextToken();
				int id = getId(writer);
				isWriter[id] = i;
				writers[i] = id;
				while (st.hasMoreTokens()) {
					String reader = st.nextToken();
					int tid = getId(reader);
					al[i].add(tid);
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < al[i].size(); j++) {
					int id = (Integer) al[i].get(j);
					if (isWriter[id] != -1) {
						map[i][isWriter[id]] = true;
					}
				}
			}
			floyd();
			solve();
		}
	}

	private void output() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j]) {
					System.out.print("1 ");
				} else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
	}

	private void floyd() {
		//output();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[j][i]) {
					for (int k = 0; k < n; k++) {
						if (map[i][k]) {
							map[j][k] = true;
						}
					}
				}
			}
		}
		//output();
	}

	private void solve() {

		Integer[] index = new Integer[n];
		for (int i = 0; i < n; i++) {
			index[i] = i;
		}
		System.out.println("--- CASE " + cas);
		cas++;
		Arrays.sort(index, 0, n, new Comparator<Integer>() {
			public int compare(Integer a, Integer b) {
				return names[writers[a]].compareTo(names[writers[b]]);
			}
		});
		for (int i = 0; i < n; i++) {
			ts[i].clear();
			for (int j = 0; j < al[i].size(); j++) {
				int v = (Integer) al[i].get(j);
				ts[i].add(names[v]);
			}
		}
		TreeSet<String> tmp = new TreeSet<String>();
		for (int i = 0; i < n; i++) {
			int p = index[i];
			int id = writers[p];
			tmp.clear();
			for (int j = 0; j < n; j++) {
				if (map[p][j] && p != j) {
					tmp.addAll(ts[j]);
				}
			}
			for (Object obj : ts[p]) {
				String str = (String) obj;
				if (tmp.contains(str)) {
					tmp.remove(str);
				}
			}
			if (tmp.size() != 0) {
				System.out.print(names[id]);
				for (String str : tmp) {
					System.out.print(" " + str);
				}
				System.out.println();
			}
		}
	}
}