[SWEA] 3952 줄 세우기

출처: [SWEA] SW 문제해결 심화 - 이산수학

 Input 

1

5 5

1 2

2 4

4 5

1 3

3 4

 

 Output 

#1 1 2 3 4 5

위상정렬 (Topological sort)  

위상정렬 (Topological sort)

 

아이들이 키를 착각하거나 잘못 주장하는 경우는 문제조건 상 없으므로

그래프 상 사이클을 확인할 필요는 없습니다.

 

※ 아래 두 문제 풀이를 참고하시면 됩니다.

- [BOJ] 2252 줄 세우기

[BOJ] 백준 2252 줄 세우기

- [BOJ] 2623 음악 프로그램

[BOJ] 백준 2623 음악프로그램

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, M;
    static Stack<integer> stack;
    static ArrayList<arraylist<integer>> adList;
    static boolean[] visited, finished;
      
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
             
            // 간선이 반드시 많은 것이 아니므로 인접 행렬 형태로 구현
            adList = new ArrayList<>();
            // 인덱스를 '1'부터 시작하기 위해 dummy data 넣어두기
            adList.add(new ArrayList<>());
            for(int i=1; i<=N; i++) {
                adList.add(new ArrayList<>());
            }
             
            // 정점의 간선을 연결한다.
            while(M-- > 0) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                adList.get(u).add(v);
            }
             
            visited = new boolean[N+1];
            finished = new boolean[N+1];
            stack = new Stack<>();
            for(int i=1; i<=N; i++) {
                DFS(i);
            }
             
            System.out.print("#" + tc + " ");
            while(!stack.isEmpty()) {
                System.out.print(stack.pop() + " ");
            }
            System.out.println();
        }
    }
     
    private static void DFS(int i) {
        if(visited[i]) return;
          
        visited[i] = true;
  
        // 해당 정점과 이어진 모든 정점을 DFS할 때까지
        while(!adList.get(i).isEmpty()) {
            DFS(adList.get(i).remove(0));    
        }
        // 연결된 지점을 모두 순회하였으므로 스택에 넣어준다.
        if(!finished[i]) {
            finished[i] = true;
            stack.push(i);    
        }
    }
}