글 읽기 - 맞았는데 왜 맞았을까요? 왜 시간초과가 안 뜰까요? (DFS 사용 풀이)

wjdwodud11 1년 전 0

DFS + DP 를 통해 문제를 해결하려다 혹시나 싶어서 그냥 DFS로 풀었더니 맞았습니다가 뜹니다.

최악의 경우 10^4(모든 컴퓨터 갯수) * 10^4(간선의 갯수) 으로 시간초과가 떠야 되는게 아닌가요?

제 코드의 경우 시간 복잡도 계산을 어떻게 해야 되는지 궁금해서 질문합니다.

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

int n,m;
int cnt = 0; // 해킹 가능한 컴퓨터 갯수

vector<int> v[10001]; // 방향 그래프 설정
vector<int> ans;// 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 저장
int maxx = -1; // 가장 많은 컴퓨터를 해킹 가능할 때 그 갯수
int visited[100001]; // 방문 체크

void dfs(int node){

    visited[node] = 1;
    cnt++;

    for (int i = 0; i < v[node].size(); i++) {

        if (!visited[v[node][i]]) {
            dfs(v[node][i]);
        }
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    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++) {

        cnt = 0;

        fill(visited, visited + n + 1, 0);
        dfs(i);


        // maxx 변수보다 cnt가 크면 maxx 초기화
        // ans 벡터 변수도 초기화
        if (maxx < cnt) {
            ans.clear();
            maxx = cnt;
            ans.push_back(i);

        } else if (maxx == cnt) {
            ans.push_back(i);
        }
    }

    sort(ans.begin(), ans.end());
    
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }

    return 0;
}