[BOJ] 1325 - 효율적인 해킹 : travelbeeee

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

---

[알고리즘풀이]

모든 1 ~ N 개의 컴퓨터에 대해서 BFS 탐색을 다 진행해 최대 탐색 가능한 컴퓨터 수를 저장한다.

그 후, 가장 큰 값을 가지고 있는 컴퓨터들만 출력하면 된다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m, x, y;
	vector<int> P[10001];
	int answer[10001] = {};
	
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		P[y].push_back(x);
	}

	int total_max = -1;
	// 1 ~ n 번까지 다 시작해보자.
	for (int i = 1; i <= n; i++) {
		// i 번에서 시작해서 BFS 탐색으로 최대 탐색 가능한 컴퓨터 수를 저장.
		int c = 1; 
		bool visited[10001] = {};
		queue<int> q;
		q.push(i);
		visited[i] = true;
		while (!q.empty()) {
			int s = q.front();
			q.pop();
			for (int j = 0; j < P[s].size(); j++) {
				if (visited[P[s][j]] == false) {
					visited[P[s][j]] = true;
					q.push(P[s][j]);
					c++;
				}
			}
		}
		answer[i] = c;
		total_max = max(total_max, c);
	}
	for (int i = 1; i <= n; i++)
		if (total_max == answer[i])
			cout << i << ' ';
}

---