047 : 효율적으로 해킹하기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 컴퓨터  A > B 신뢰 == B를 해킹하면 A도 해킹가능 한 번에 가장 많은 컴퓨터를 해킹 할 수 있는 번호를 출력하라	신뢰도 배열을 만든 후 BFS	I // N(컴퓨터 갯수) M(신뢰 관계 수) A(1) B(1)(A > B 신뢰) ... A(M) B(M) O // 한번에 가장 많은 컴퓨터 해킹할 수 있는 번호를 오름차순 출력

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    // Preprocessing
    static int N, M;
    static boolean visited[];
    static int answer[];
    static ArrayList<Integer> A[];

    public static void main(String[] args) throws IOException {

        // Input Supply Cable
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // Preprocessing
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new ArrayList[N+1];
        answer = new int[N+1];
        for (int i = 1; i <= N; i++){
            A[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            A[S].add(E);
        }

        // Operating BFS
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N+1];
            BFS(i);
        }
        int max = 0;
        for (int i = 1; i < N; i++) {
            max = Math.max(max, answer[i]);
        }
        
        
        // Output Extracting Cable
        for (int i = 1; i <= N; i++) {
            if (answer[i] == max)
                System.out.print(i + " ");
        }
    }
    
    // External Module BFS
    public static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(index);
        visited[index] = true;
        while (!queue.isEmpty()) {
            int now_Node = queue.poll();
            for (int i : A[now_Node]) {
                if (!visited[i]) {
                    visited[i] = true;
                    answer[i]++;
                    queue.add(i);
                }
            }
        }
        
    }

    
}