백준 2623번: 음악프로그램 [위상정렬] - Java

https://www.acmicpc.net/problem/2623

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int cnt = 0;
		List<Integer> list[] = new List[N+1];
		int indegree[] = new int[N+1];
		Queue<Integer> q = new LinkedList<Integer>();
		
		for (int i = 1; i < N+1; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int sum = Integer.parseInt(st.nextToken());
			int A = 0;
			for (int j = 0; j < sum; j++) {
				int B = Integer.parseInt(st.nextToken());
				if(A>0) {
					list[A].add(B);
					indegree[B]++;
				}
				A = B;
			}
		}
		
		for (int i = 1; i < N+1; i++) {
			if(indegree[i]==0)
				q.add(i);
		}
		StringBuilder sb = new StringBuilder();
		
		while(!q.isEmpty()) {
			int num = q.poll();
			sb.append(num+"\n");
			cnt++;
			
			for(int n : list[num]) {
				indegree[n]--;
				if(indegree[n]==0) {
					q.add(n);
				}
			}
		}
		
		if(cnt<N)
			System.out.println(0);
		else
			System.out.println(sb);

	}

}