백준 1325번 효율적인 해킹 C++

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

A가 B를 신뢰하는 경우에 B를 해킹하면 A를 해킹할 수 있기 때문에

A와 B를 입력받았을 때 B->A 로 연결되어있다고 저장한 뒤 bfs로 탐색하여 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, m;
vector<vector<int>> trust(10001, vector<int>());

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		trust[b].push_back(a);
	}
	int max_cnt = -1;
	vector<int> ans;
	for (int i = 1; i <= 10000; i++) {
		bool visited[10001] = { false };
		visited[i] = true;
		int cnt = 0;
		queue<int> q;
		q.push(i);
		while (!q.empty()) {
			auto curr = q.front();
			q.pop();
			cnt++;
			for (auto next : trust[curr]) {
				if (!visited[next]) {
					q.push(next);
					visited[next] = true;
				}
			}
		}
		if (cnt == max_cnt) {
			ans.push_back(i);
		}
		else if (cnt > max_cnt) {
			ans.clear();
			ans.push_back(i);
			max_cnt = cnt;
		}
	}
	sort(ans.begin(), ans.end());
	for (auto val : ans) {
		cout << val << "\n";
	}
};