효율적인 해킹

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

int n, m;

vector<int> map[100001];

bool d[100001];

int cnt;



void dfs(int node)
{
    d[node] = true;
    
    for (int i = 0; i < map[node].size(); i++)
    {
        int next = map[node][i];
        if (!d[next])
        {
            cnt++;
            dfs(next);
        }
    }
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    
    for (int i = 0; i < m; i++){
        int node1, node2;
        cin >> node1 >> node2;
        map[node2].push_back(node1);
    }
    
    int nodeCnt = 0;
    vector<int> result;
    
    for (int i = 1; i <= n; i++)
    {
        memset(d, false, sizeof(d));
        cnt = 0;
        dfs(i);
        if (nodeCnt == cnt)
            result.push_back(i);
        if (nodeCnt < cnt)
        {
            nodeCnt = cnt;
            result.clear();
            result.push_back(i);
        }
    }
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
    cout << endl;

    return 0;

}

 

DFS문제다.

BFS로하면 풀기힘들다.

간선벡터로 잡아놔서 Bool배열 초기화를시키기위해선 2차원으로 만들어야하는데

2차원배열 초기화시키는거 + 2차원배열왔다갔다하는거 하면 시간복잡도가 터지는모양이다.

그냥 1차원배열로 한큐에풀게 DFS로 풀어봤다.