데일리썽

문제 제목 : 효율적인 해킹

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main8 {
    public static int pcCnt, connCnt, hackingCnt, maxHackingCnt;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[10001];

    public static Integer bfs(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(node);
        visited = new boolean[10001];
        visited[node] = true;

        hackingCnt = 1;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int adjNode : adjList.get(now)) {
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                    hackingCnt++;
                }
            }
        }

        return hackingCnt;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        pcCnt = Integer.parseInt(st.nextToken());
        connCnt = Integer.parseInt(st.nextToken());

        for (int i = 0; i < pcCnt + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < connCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int pc1 = Integer.parseInt(st.nextToken());
            int pc2 = Integer.parseInt(st.nextToken());
            adjList.get(pc2).add(pc1);
        }

        maxHackingCnt = 0;
        List<Integer> resultList = new ArrayList<Integer>();
        for (int i = 1; i < pcCnt + 1; i++) {
            int cnt = bfs(i);

            if (cnt > maxHackingCnt) {
                maxHackingCnt = cnt;
                resultList = new ArrayList<>();
                resultList.add(i);
            } else if (cnt == maxHackingCnt) {
                resultList.add(i);
            }
        }

        for (Integer result : resultList) {
            System.out.print(result + " ");
        }
    }
}