[Java] 백준 2623번 음악프로그램

위상 정렬 문제입니다.

가수들간의 출연 순서들이 정해집니다. 관계를 A->B의 형태로 배열에 저장합니다.
size배열을 만들어서 B로 지목되는 경우 크기를 1개씩 늘려줍니다.

size배열이 0인 경우 해당 가수보다 먼저 출연해야되는 사람이 없는 경우이므로
0인 경우부터 큐에 넣어서 BFS방식으로 탐색하였습니다.

탐색을 하다가 size가 2가 넘는 경우 먼저 출연해야하는 사람이 현재 사람 말고 더 있는 경우이므로 size만 1 줄여주고 큐에 넣지 않습니다.

싸이클이 발생할 경우 0으로 해주어야하므로 일정 수 이상 끝나지 않거나 모든 가수를 출력하지 못하는 경우 0을 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int c = 0;
		int[] size = new int[n + 1];
		Queue<Integer> q = new LinkedList<>();
		Queue<Integer> testQ = new LinkedList<>();
		ArrayList<ArrayList<Integer>> al = new ArrayList<>();

		for (int i = 0; i <= n; ++i) {
			ArrayList<Integer> temp = new ArrayList<>();
			al.add(temp);
		}

		for (int i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			for (int j = 1; j < cnt; ++j) {
				int b = Integer.parseInt(st.nextToken());
				al.get(a).add(b);
				++size[b];
				a = b;
			}
		}

		for (int i = 1; i <= n; ++i) {
			if (size[i] == 0) {
				q.add(i);
				testQ.add(i);
			}
		}
		
		while (!q.isEmpty()) {
			if(c > n) {
				break;
			}
			int index = q.poll();
			if (size[index] > 1) {
				--size[index];
				continue;
			}
			++c;
			sb.append(index).append("\n");
			for (int i = 0; i < al.get(index).size(); ++i) {
				q.add(al.get(index).get(i));
			}
		}
		if(c == n) {
			bw.write(sb + "");
		} else {
			bw.write(0 + "");
		}
		bw.close();
	}
}