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

solution

단방향 그래프

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


int N, M;
vector<int> G[10001];
int visited[10001] = { 0, };
int cnt;

void dfs(int node) {
	//방문
	visited[node] = 1;
	cnt += 1;
	
	for (int i = 0; i < G[node].size(); i++) {
		if (visited[G[node][i]] == 0) {
			dfs(G[node][i]);
		}
	}

}

int main()
{
	cin >> N >> M;
	while (M--) {
		int c1, c2;
		cin >> c1 >> c2;
		G[c2].push_back(c1);
	}

	int max_ = 0;
	vector<int> ans;

	for (int i = 1; i <= N; i++) {
		//방문 0으로 초기화
		for (int j = 1; j <= N; j++)
			visited[j] = 0;
		cnt = 0;

		if (visited[i] == 0) {
			dfs(i);
			if (cnt > max_) {
				ans.clear();
				ans.push_back(i);
				max_ = cnt;
			}
			else if (cnt == max_) {
				ans.push_back(i);
			}
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		
		if (i != ans.size() - 1)
			cout << ans[i] << " ";
		else
			cout << ans[i];
	}
}