백준_2252 줄 세우기 (위상정렬)Algorithm/Algorithm 문제2024. 2. 19. 15:02
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ_2252_줄세우기 {
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());
int[] inDegree = new int[n+1];
ArrayList<Integer>[] arr = new ArrayList[n+1];
for (int i=1; i<n+1; i++) {
arr[i] = new ArrayList<>();
}
int a, b;
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
arr[a].add(b);
inDegree[b]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i=1; i<n+1; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
StringBuilder sb = new StringBuilder();
int nowNode;
while (!queue.isEmpty()) {
nowNode = queue.poll();
sb.append(nowNode).append(' ');
for (int nextNode : arr[nowNode]) {
if (--inDegree[nextNode] == 0) {
queue.add(nextNode);
}
}
}
System.out.println(sb);
}
}
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1948 임계경로 (위상정렬, 에지 뒤집기) (0) | 2024.02.21 |
---|---|
백준_1516 게임 개발 (위상정렬) (0) | 2024.02.20 |
백준_1043 거짓말 (유니온파인드) (0) | 2024.02.18 |
백준_1976 여행 가자 (유니온파인드) (0) | 2024.02.17 |
백준_1717 집합의 표현 (유니온파인드) (0) | 2024.02.16 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!