[Java] 백준 2252 - 줄 세우기

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

 

---

풀이

위상정렬 기초 문제.

(키 작은 사람) → (키 큰 사람)  이렇게 간선을 이어주고

indegree가 0인 노드를 하나씩 지워나가는 식으로 정렬하기.

 

---

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		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());
		ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
		int[] indegree = new int[N + 1];

		for (int i = 0; i <= N; i++) {
			adj.add(new ArrayList<>());
		}

		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			adj.get(A).add(B);
			indegree[B]++;
		}

		Queue<Integer> que = new LinkedList<>();
		StringBuilder result = new StringBuilder();
		int cnt = 0;

		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				que.add(i);
			}
		}

		while (!que.isEmpty()) {
			int cur = que.remove();
			result.append(cur).append(' ');
			cnt++;

			for (int next : adj.get(cur)) {
				if (--indegree[next] == 0) {
					que.add(next);
				}
			}
		}

		if (cnt < N) {
			System.out.println("Cycle detected");
		} else {
			System.out.println(result);
		}

		br.close();
	}
}