sortingitallout_solve2.java

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

import java.util.*;
/**
 * ID:1094
 * 标准拓扑排序，首先遍历得到入度，随后拓扑
 * 对于本题无法使用
 * @author yhm
 *
 */
public class SortingItAllOut_solve2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int size = cin.nextInt();
			int num = cin.nextInt();
			if(size==0 && num==0){
				break;
			}
			
			boolean[][] E = new boolean[size][size];
			for(int j=0;j<size;j++){
				Arrays.fill(E[j], false);
			}
			int[] V = new int[size];
			Arrays.fill(V, -1);
			
			for(int i=0;i<num;i++){
				String str = cin.next();
				String[] str1 = str.split("<");
				char ch1 = str1[0].charAt(0);
				char ch2 = str1[1].charAt(0);
				E[ch1-'A'][ch2-'A'] = true;
			}
			setIndegree(V, E, size);
			solve(V, E, size, num); 
		}

	}
	
	static void solve(int[] V, boolean[][] E, int size, int num){
		Stack<Integer> stack = new Stack<Integer>();
		StringBuffer str = new StringBuffer("");
		for(int v=0;v<size;v++){
			if(V[v]==0){
				stack.push(v);
			}
		}
		//有环则有时栈为空
		while(!stack.isEmpty()){
			if(stack.size()!=1){

				System.out.println("Sorted sequence cannot be determined.");
				return;
			}
			else{
				int v = stack.pop();
				char ch = (char)(v+'A');
				str.append(ch);
				for(int w=0;w<size;w++){
					if(E[v][w]){
						V[w]--;
						if(V[w]==0){
							stack.push(w);
						}
					}
				}
			}
		}
		if(str.length()!=size){
			System.out.println("Inconsistency found after "+num+" relations.");
		}
		else{
			System.out.println(str.toString());
		}
	}
	
	static void setIndegree(int[] V, boolean[][] E, int size){
		int i=0;
		while(i<size && V[i]==-1){
			DFS(V, E, i, size);
			i++;
		}
	}
	
	static void DFS(int[] V, boolean[][] E, int v, int size){
		if(V[v] == -1){
			V[v] = 0;
		}
		for(int i=0;i<size;i++){
			if(E[v][i]){
				if(V[i]==-1){
					DFS(V, E, i, size);
				}
				V[i]++;
			}
		}
	}

}