欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【拓扑排序】系谱图 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();
        }
    }
}