[1325] 효율적인 해킹

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

1325번: 효율적인 해킹

<문제>

bfs dfs 어느 쪽이든, 모든 컴퓨터를 시작으로 삼아 탐색을 진행해주고 결과를 아래처럼 저장해둔다.

res[i] = i번 컴퓨터를 시작으로 할 때 방문할 수 있는 정점의 개수 

n번의 브루트포스적인 탐색으로, res[1~n]을 채웠다면 다시 순회하여 최댓값을 찾고

또다시 순회하여 res[i] == max를 만족하는 i를 출력하면 되겠다.

 

<소스코드>

#include <stdio.h>
#include <string.h>
 
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[10001];
queue<int> q;
int n, m;
int f(int s) {
    int i, cnt, cur;
    bool visit[10001];
    memset(visit, false, sizeof(visit));
    q.push(s);
    visit[s] = true;
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        for (i = 0; i < v[cur].size(); i++) {
            int next = v[cur][i];
            if (visit[next]) continue;
            q.push(next);
            visit[next] = true;
        }
    }
    cnt = 0;
    for (i = 1; i <= n; i++) {
        if (visit[i]) cnt++;
    }
    return cnt;
}
int main(void) {
    int i, res[10001] = {0}, max_cnt = 0;
    scanf("%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        v[b].push_back(a);
    }
    for (i = 1; i <= n; i++) {
        res[i] = f(i);
        max_cnt = max(max_cnt, res[i]);
    }
    for (i = 1; i <= n; i++)
        if (res[i] == max_cnt) printf("%d ", i);
    return 0;
}