1325번

1325번 - 효율적인 해킹

A가 B를 신뢰하면, B를 해킹 했을 때 A를 해킹할 수 있다.

따라서 A노드와 B노드를 만들고 B->A로 가는 간선을 추가한 뒤, 모든 노드들에 대해서 DFS를 탐색한다.

그래서 방문할 수 있는 노드가 가장 많은 시작점이 답이 된다.

따라서 간선을 설정하고, 모든 노드를 방문하면서 DFS를 돌린다. 그 후에 가장 방문을 많이 한 지점을 찾아서 출력해주면 된다.

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
 
bool check[10001];
void dfs(int here,vector<vector<int>> &v)
{
    check[here] = true;
 
    for (int i = 0; i < v[here].size(); i++)
    {
        int there = v[here][i];
        if (!check[there])
        {
            check[there] = true;
            dfs(there, v);
        }
    }
}
int main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    vector<int> x;
    vector<vector<int>> v(n+1);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[b].push_back(a);
    }
 
    for (int i = 1; i <= n; i++)
    {
        memset(check, false, sizeof(check));
        dfs(i,v);
        int k = 0;
        for (int j = 1; j <= n; j++)
        {
            if (check[j]) k++;
        }
 
        if (k > ans)
        {
            ans = k;
            x.clear();
            x.push_back(i);
        }
        else if (k == ans)
        {
            x.push_back(i);
        }
    }
 
    for (int i = 0; i < x.size(); i++)
    {
        cout << x[i] << " ";
    }
    cout << "\n";
    return 0;
}