sortingitallout.java

PKU中一些数据结构基本算法题的java实现

import java.util.*;

/**
 * ID:1094
 * 拓扑排序，首先将可以连接的边连起来（如A>B,B>C则有A>C,则map[1][3]为1），随后按照入度排序输出
 * @author yhm
 *
 */
public class SortingItAllOut {

	static int[] sorted;
	static int[][] map;
	static String[] str;

	public static void main(String[] args) {
		int n, m;
		int t;
		int i, j, k;
		Scanner cin = new Scanner(System.in);
		L2: while (cin.hasNext()) {

			n = cin.nextInt();
			m = cin.nextInt();
			if (n == 0 && m == 0) {
				break;
			}

			map = new int[n+1][n+1];
			sorted = new int[n+1];
			str = new String[m+1];
			
			for (t = 1; t <= m; t++) {
				str[t] = cin.next();
			}

			for (t = 0; t <= n; t++) {
				Arrays.fill(map[t], 0);
			}

			L: for (t = 1; t <= m; t++) {
				i = str[t].charAt(0) - 'A' + 1;
				j = str[t].charAt(2) - 'A' + 1;
				switch (str[t].charAt(1)) {
				case '>':
					if (map[i][j] == -1 || map[j][i] == 1) {
						System.out.print("Inconsistency found after " + t
								+ " relations.\n");
						continue L2;
					}
					map[i][j] = 1;
					map[j][i] = -1;
					break;
				case '<':
					if (map[i][j] == 1 || map[j][i] == -1) {
						System.out.print("Inconsistency found after " + t
								+ " relations.\n");
						continue L2;
					}
					map[i][j] = -1;
					map[j][i] = 1;
					break;
				}

				for (k = 1; k <= n; k++)
					for (i = 1; i <= n; i++)
						for (j = 1; j <= n; j++) {
							if (map[i][k] != 0 && map[k][j] != 0 && k != i
									&& i != j) {
								if (map[i][j] == 0) {
									//有间接的从i到j的方式？
									if (map[i][k] == map[k][j]) {
										map[i][j] = map[i][k];
										map[j][i] = -map[i][k];
									}
								} else {
									//可能有环
									if (map[i][k] == map[k][j]) {
										//有环？
										if (map[i][k] != map[i][j]) {
											System.out
													.print("Inconsistency found after "
															+ t
															+ " relations.\n");
											continue L2;
										}
									}
								}
							}
						}

				for (i = 1; i <= n; i++) {
					int p = 1;
					for (j = 1; j <= n; j++) {
						if (i != j) {
							//现有的规则可以确定了么
							if (map[i][j] == 0) {
								//不可以
								continue L;
							}
							if (map[i][j] == 1)
								p++;
						}
					}
					sorted[p] = i;
				}

				System.out.print("Sorted sequence determined after " + t
						+ " relations: ");
				for (i = 1; i <= n; i++)
					System.out.print((char) (sorted[i] + 'A' - 1));
				System.out.print(".\n");
				continue L2;
			}

			System.out.print("Sorted sequence cannot be determined.\n");

			continue;

		}
	}
}