🖊️ 문제

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

---

🖊️ 풀이

DFS 문제..
기본적인 DFS 문제이긴한데 visited 내부 체크를 잘못해서 오래걸렸다 ㅠㅠ

vector<int> vec[]를 전역으로 사용햇고,

예제 입력1 기준으로

1 : 3
2 : 3
3 : 4, 5
4 : 
5 : 

이렇게 가리키도록 설정했다.
그래서 1번부터 시작해서 DFS를 돌면서, 연결된 애들의 총 숫자를 리턴하게 했다.
DFS 돈 후에는 visited 다시 False로 바꿔주고..

그렇게 하고 인덱스가 필요하므로 pair로 저장해줌.
처음에는 pair로 저장한 result 벡터 자체를 정렬해서 앞에 몇개만 출력하는 형태로 했는데,
시간초과되므로 걍 최대값maxHack을 구해서,
순차탐색하면서 최댓값과 second가 같으면 출력하게 했다.

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

vector<int> vec[10'001];
bool visited[10'001] = { false, };
int hack[10'001];

int DFS(int n)
{
	int result = 1;
	visited[n] = true;
	if (vec[n].empty()) return 1;
	for (int& vin : vec[n]) {
		if (!visited[vin]) {
			result += DFS(vin);
		}
	}
	return result;
}

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

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		vec[b].push_back(a);
	}

	vector<pair<int, int>> result;
	int maxHack = -1;
	for (int i = 1; i <= n; i++) {
		int canHack = DFS(i);
		memset(visited, false, sizeof(visited));
		maxHack = max(maxHack, canHack);
		result.emplace_back(make_pair(i, canHack));
	}

	for (auto& r : result) {
		if (r.second == maxHack) cout << r.first << " ";
	}
}