인프런 커뮤니티 질문&답변

안녕하세요 상훈님 ㅎㅎ

제가 상훈님 코드에 주석으로 설명해드렸습니다.

참고 부탁드립니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>
#include <map>
#include <stack>
using namespace std;
vector<int> adj[100001];
int visited[100001];
int n, m, cnt, ret = 1;
int a, b;

void dfs(int node)
{
	visited[node] = 1;
	for (int i = 0; i < adj[node].size(); i++)
	{
		if (!visited[adj[node][i]])
		{
			cnt++;
			dfs(adj[node][i]);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
    //인접리스트로 잘 하셧습니다.   
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		adj[b].push_back(a);
	}

// 자 이렇게 dfs를 돌렸죠? 해당 idx에 해당하는 cnt를 어떠한 배열에다가 담아야 합니다.
// 배열에 담게 되면 다시 for문 돌리면서 dfs를 할 필요가 없게 됩니다. mx[i] = cnt 이렇게 하고 이 mx[]를
// 나중에 비교하는 것이죠.
	for (int i = 1; i <= n; i++)
	{
		fill(&visited[0], &visited[0] + 100001, 0);
		cnt = 0;
		dfs(i); 
		ret = max(ret, cnt);
		
	}
// 이 로직은 다시 dfs를 하죠? 이러한 로직이 추가가 되었기 때문에 시간초과가 나는 것 같습니다.  
	for (int i = 1; i <= n; i++)
	{
		fill(&visited[0], &visited[0] + 100001, 0);
		cnt = 0;
		dfs(i);

		if (cnt == ret)
			cout << i << " ";
	}

	
	return 0;

}

또 질문이 있으시다면 언제든지 질문 부탁드립니다.

또한 제 강의가 마음에 드셨다면 좋은 수강평과 별점 5점 꾹 부탁드립니다 :)

감사합니다.

강사 큰돌 올림.