[BOJ/C++] 1325 효율적인 해킹 : DFS

문제

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

풀이

"A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다"
➡️방향그래프
➡️거꾸로 생각해서 인접리스트를 만들어야 함

코드

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

using namespace std;

vector<int> v[10001];
bool check[10001];
int cnt;

void dfs(int node) {
	check[node] = true;

	for (int i = 0; i < v[node].size(); i++) {
		int next = v[node][i];
		if (!check[next]) {
			cnt++;
			dfs(next);
		}
	}
}

int main() {
	int N, M;
	vector<int> ans;
	
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		v[tmp2].push_back(tmp1);
	}

	for (int i = 1; i <= N; i++) {
		dfs(i);
		ans.push_back(cnt);
		fill_n(check, 10001, false);
		cnt = 0;
	}

	int max = *max_element(ans.begin(), ans.end());
	for (int i = 0; i < N; i++) {
		if (ans[i] == max) {
			cout << i + 1 << ' ';
		}
	}

	return 0;
}