2-S 재질문 드립니다 :)

작성한 질문수 79

1

안녕하세요 유태님 ㅎㅎ

int DFS(int idx)
{
	int cnt = 1;

	for (const auto& v : vec[idx])
	{
		cnt += DFS(v);
	}

	return cnt;
}

이럴 경우 사이클이 있는 경우 무한 탐색이 되버립니다.

	for (int i = 1; i <= N; i++)
	{
		if (mx == DFS(i)) cout << i << " ";
	}

이럴 경우에 if문 실행시 DFS가 실행되는데 이렇게 하면 상상한 DFS가 올바르게 동작하지 않습니다. visited 초기화 -> DFS 이렇게 구축해야 합니다.

temp 배열이 DP 말씀하시는 것 같은데요. 이렇게 결과값을 모아두어야 불필요하게 반복되는 DFS를 방지할 수 있습니다

#include <bits/stdc++.h>
using namespace std;
 
vector<int> v[10001];
int dp[10001], mx, visited[10001], n, m, a, b;
 
int dfs(int here) {  
	visited[here] = 1;
	int ret = 1; 
	for(int there : v[here]){
		if(visited[there]) continue;
		ret += dfs(there); 
	} 
	return ret;
}
 
int main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> n >> m;  
	while (m--) {
     	cin >> a >> b;  
	    v[b].push_back(a);
	} 
	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dp[i] = dfs(i); 
		mx = max(dp[i], mx);
	} 
	for (int i = 1; i <= n; i++) if (mx == dp[i]) cout << i << " "; 
	return 0;
}

감사합니다.