package code;

import java.util.ArrayList;
import java.util.List;

public class Code210 {
	/*
	 * top排序
	 */
 public int[] findOrder(int numCourses, int[][] prerequisites) {
 int i;
 int[] ans=new int[numCourses];
 List<List<Integer>> inEdge=new ArrayList<List<Integer>>();
 List<List<Integer>> outEdge=new ArrayList<List<Integer>>();
 
 for(i=0;i<numCourses;i++){
 	inEdge.add(new ArrayList<Integer>());
 	outEdge.add(new ArrayList<Integer>());
 }
 
 for(i=0;i<prerequisites.length;i++){
 	int a=prerequisites[i][0];
 	int b=prerequisites[i][1];
 	inEdge.get(a).add(b);
 	outEdge.get(b).add(a);
 }
 int cnt=0;
 boolean[] vis=new boolean[numCourses];
 
 while(true){
 	List<Integer> list=new ArrayList<Integer>();
 	for(i=0;i<numCourses;i++){
 		//入度为0
 		if(!vis[i] && inEdge.get(i).size()==0){
 			list.add(i);
 			ans[cnt++]=i;
 			vis[i]=true;
 		}
 	}
 	if(cnt==numCourses)
 		break;
 	if(list.size()==0)
 		return new int[0];
 	/*
 	 * 将入度为0的点删掉
 	 */
 	for(i=0;i<list.size();i++){
 		int x=list.get(i);
 		for(int j=0;j<outEdge.get(x).size();j++){
 			int y=outEdge.get(x).get(j);
 			for(int k=0;k<inEdge.get(y).size();k++){
 				if(inEdge.get(y).get(k)==x)
 				{
 					inEdge.get(y).remove(k);
 					break;
 				}
 			}
 		}
 	}
 }
 return ans;
 }
 /*
 * 207,检查是否不能top排序的
 */
 public boolean canFinish(int numCourses, int[][] prerequisites){
 int i;
 int[] ans=new int[numCourses];
 List<List<Integer>> inEdge=new ArrayList<List<Integer>>();
 List<List<Integer>> outEdge=new ArrayList<List<Integer>>();
 
 for(i=0;i<numCourses;i++){
 	inEdge.add(new ArrayList<Integer>());
 	outEdge.add(new ArrayList<Integer>());
 }
 
 for(i=0;i<prerequisites.length;i++){
 	int a=prerequisites[i][0];
 	int b=prerequisites[i][1];
 	inEdge.get(a).add(b);
 	outEdge.get(b).add(a);
 }
 int cnt=0;
 boolean[] vis=new boolean[numCourses];
 
 while(true){
 	List<Integer> list=new ArrayList<Integer>();
 	for(i=0;i<numCourses;i++){
 		//入度为0
 		if(!vis[i] && inEdge.get(i).size()==0){
 			list.add(i);
 			ans[cnt++]=i;
 			vis[i]=true;
 		}
 	}
 	if(cnt==numCourses)
 		break;
 	if(list.size()==0)
 		return false;
 	/*
 	 * 将入度为0的点删掉
 	 */
 	for(i=0;i<list.size();i++){
 		int x=list.get(i);
 		for(int j=0;j<outEdge.get(x).size();j++){
 			int y=outEdge.get(x).get(j);
 			for(int k=0;k<inEdge.get(y).size();k++){
 				if(inEdge.get(y).get(k)==x)
 				{
 					inEdge.get(y).remove(k);
 					break;
 				}
 			}
 		}
 	}
 }
 return true;
 }
 
 public static void main(String[] args){
 	int[][] p={{1,0},{2,0},{3,1},{3,2}};
 	new Code210().findOrder(4, p);
 }
}