효율적인 해킹 - 1325

//1325 - 효율적인 해킹
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> hacked;
 
void init()
{
    cin >> N >> M;
    adj = vector<vector<int>>(N+1);
    hacked = vector<int>(N+1);
    int x, y;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y;
        adj[y].push_back(x);
    }
}
 
int dfs(int here)
{
    visited[here] = true;
    int ret = 1;
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i];
        if(!visited[there])
            ret += dfs(there);
    }
    return ret;
}
 
void dfsAll()
{
    int big = 0;
    for(int i = 1; i<=N; ++i)
    {
        visited = vector<bool>(N+1, false);
        int t = dfs(i);
        big = max(big, t);
        hacked[i] = t;
    }
    for(int i = 1; i<=N; ++i)
        if(big == hacked[i])
            cout << i << " ";
}
 
int main()
{
    init();
    dfsAll();
}

 

 

 

 

 

 

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

1325번: 효율적인 해킹

 

 

 

 

 

 

효율적인 해킹

모든 정점에 대해 DFS를 돌리면 되는 문제였습니다..

DFS시간복잡도 * 전체 정점 개수를 하면 10억이기에 5초안에 안풀릴줄 알았는데 풀리네용~