【拓扑排序】系谱图 POJ2367
程序员文章站
2024-03-19 10:03:28
...
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class Main{
static Scanner input = new Scanner(System.in);
public static void main(String[] args){
int people = input.nextInt();
node[] data = new node[people+1];
int[] inadd = new int[people+1];
for(int i=1;i<=people;i++){
data[i] = new node(i);
do{
int temp = input.nextInt();
if(temp==0)break;
data[i].out.add(temp);
inadd[temp]++;
}while(true);
}
for(int i=1;i<=people;i++){
data[i].in = inadd[i];
}
LinkedList<node> list = new LinkedList();
for(int i=1;i<=people;i++){
//把一开始是0的丢进队列
if(data[i].in==0){
list.add(data[i]);
}
}
ArrayList<Integer> ans = new ArrayList();
while(!list.isEmpty()){
node temp = list.poll();
ans.add(temp.id);
for(int i=0;i<=temp.out.size()-1;i++){
data[temp.out.get(i)].in--;
if(data[temp.out.get(i)].in==0)list.add(data[temp.out.get(i)]);
}
}
for(int i=0;i<=ans.size()-1;i++){
System.out.print(ans.get(i));
if (i!=ans.size()-1) System.out.print(" ");
}
}
static class node{
int in = 0;
int id;
ArrayList<Integer> out;
node(int id){
this.id = id;
out = new ArrayList();
}
}
}