[C++] 백준 1325번 효율적인 해킹

문제 링크

1325번: 효율적인 해킹

문제 요약

그래프의 각 정점으로부터 도달할 수 있는 정점의 수가 최대인 정점들을 구해야 한다.

접근 방법

문제를 처음 봤을 때는 시간 제한을 제대로 보지 않아서 강한 연결 요소를 생각하고 있었습니다.
하지만 시간 제한이 5초나 되는 것을 확인하고 그래프 탐색을 N번 돌리는 풀이를 바로 생각할 수 있었습니다.

1. N개의 정점들 각각을 시작점으로 DFS 또는 BFS를 하며 방문 가능한 정점의 수를 기록한다.
2. 방문 가능한 정점 수의 최댓값을 찾는다.
3. 최댓값과 방문 가능한 정점 수가 일치하는 정점들의 번호를 모두 출력한다.

간단한 그래프 탐색 문제이고 많이 풀린 문제이지만 정답률은 특이하게도 매우 낮은 편이었습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 10001

using namespace std;


int max_;
bool visited[MAX];
vector<int> cnt(MAX), adj[MAX];

void bfs(int start, vector<int>& v)
{
	queue<int> q;
	q.push(start);
	visited[start] = true;
	
	int cnt = 0;
	while (!q.empty())
	{
		cnt++;
		int now = q.front();
		q.pop();

		for (auto& next : adj[now])
			if (!visited[next])
				q.push(next), visited[next] = true;
	}

	v[start] = cnt;
	max_ = max(max_, cnt);
}

int main(void)
{
	FASTIO;

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

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

	for (int i = 1; i <= n; i++)
		memset(visited, false, sizeof(visited)), bfs(i, cnt);

	for (int i = 1; i <= n; i++)
		if (cnt[i] == max_)
			cout << i << ' ';
	return 0;
}