1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int dx = 0, dy = 0;
for(int i=1; i<= M; i++) {
st = new StringTokenizer(br.readLine());
dx = Integer.parseInt(st.nextToken());
dy = Integer.parseInt(st.nextToken());
adj[dx].add(dy);
indegree[dy]++; // 선행되어야할 노드 갯수 세기
}
for(int i=1; i<= N; i++) { // ingegree == 0 은 선행되어야 할 노드
if(indegree[i] == 0) que.add(i); // 전부 처리되었으니 진행 가능 !
}
int flag = 0; // flag == N 이면 위상정렬 완료
// flag > N 사이클 존재 !
// flag < N 위상정렬 불가능
while(!que.isEmpty()) {
int cur = que.poll();
flag++;
bw.write(cur + " ");
for(int next : adj[cur]) {
indegree[next]--;
if(indegree[next] == 0) {
que.add(next);
}
}
}
백준 2252 줄세우기, 1766 문제집, 2623 음악프로그램, 1516 게임 개발, 1005 acm craft, 9470 strahler 순서