• 방향이 존재하는 유향 그래프(Directed Graph)
  • N이 최대 100이기 때문에 인접 행렬 사용
  • vertex를 bfs로 접근
  • 마지막에 받는 사람들 중 번호가 가장 큰 것이 답이기 때문에 depth 계산이 필요


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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63



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

public class Solution {
	static final int MAX_N = 101;
	static boolean[][] edge;
	static int[] visited;
	static int res;

	static int bfs(int start) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(start);
		visited[start] = 1;
		int cnt = 2;
		while (!q.isEmpty()) {
			for (int qs = 0, qSize = q.size(); qs < qSize; qs++) {
				int from = q.poll();
				for (int to = 1; to < MAX_N; to++) {
					if \(!edge\[from]\[to] \|| visited\[to] > 0)
						continue;

					visited[to] = cnt;
					q.offer(to);
				}
			}
			cnt++;
		}
		
		int maxCnt = 1;
		int maxNum = start;
		for (int i = 1; i < 101; i++) {
			if (maxCnt == visited[i])
				maxNum = Math.max(maxNum, i);
			if (maxCnt < visited[i]) {
				maxCnt = visited[i];
				maxNum = i;
			}
		}
		return maxNum;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for (int tc = 1; tc <= 10; tc++) {
			res = 1;
			edge = new boolean[MAX_N][MAX_N];
			visited = new int[MAX_N];

			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int start = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(in.readLine(), " ");
			for (int i = 0; i < N/2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				edge[from][to] = true;
			}
			System.out.println("#" + tc + " " + bfs(start));
		}
	}
}