본인 풀이

시간초과 발생

#include<bits/stdc++.h>
using namespace std;

// n은 컴퓨터, m은 간선 수
int n, m;
vector<int> v[10001];
map<int, int> mp;

// 그래프 뎁스가 깊어질수록 해킹 가능한 컴퓨터 수 + 1
void dfs(int here, int depth){
    mp[here] = depth;
    for (int there : v[here]){
        dfs(there, depth + 1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        int here, there;
        cin >> here >> there;
        v[here].push_back(there);
        mp[here] = 0;
    }

    for(auto it : mp){
        for (int val : v[it.first]){
            dfs(val, 1);
        }
    }

    int mx = 0;
    vector<int> mxVal;
    for (auto it : mp){
        if(it.second == mx){
            mxVal.push_back(it.first);
        }else if(it.second > mx){
            mxVal.clear();
            mxVal.push_back(it.first);
        }

        mx = max(mx, it.second);
    }

    sort(mxVal.begin(), mxVal.end());

    for(int i : mxVal){
        cout << i << " ";
    }
    cout << "\n";

    return 0;
}

1. 시작지점으로부터 DFS로 트리순회를 진행할때의 뎁스가 해킹 가능한 컴퓨터 숫자라고 판단하였음.

#include<bits/stdc++.h>
using namespace std;

// n은 컴퓨터, m은 간선 수
int n, m;
vector<int> v[10001];
int visited[10001];
map<int, int> mp;

// 그래프 뎁스가 깊어질수록 해킹 가능한 컴퓨터 수 + 1
void dfs(int here, int depth){
    visited[here] = 1;

    mp[here] = depth;
    for (int there : v[here]){
        // 방문하지 않은곳이라면
        if(mp[there] == 0){
            dfs(there, depth + 1);
        }else{
            // 다른곳으로부터 연결된 노드 컴포넌트가 더 크면 더 볼필요 없음
            if(mp[there] > mp[here]){
                continue;
            }else{
                dfs(there, mp[here] + 1);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        int here, there;
        cin >> here >> there;
        v[here].push_back(there);
        mp[here] = 0;
    }

    for(auto it : mp){
        for (int val : v[it.first]){
            dfs(val, 1);
        }
    }

    int mx = 0;
    vector<int> mxVal;
    for (auto it : mp){
        if(it.second == mx){
            mxVal.push_back(it.first);
        }else if(it.second > mx){
            mxVal.clear();
            mxVal.push_back(it.first);
        }

        mx = max(mx, it.second);
    }

    sort(mxVal.begin(), mxVal.end());

    for(int i : mxVal){
        cout << i << " ";
    }
    cout << "\n";

    return 0;
}

1. 로직 개선후 재풀이 진행했지만 여전히 시간초과 발생
2. 내가 이동하려는 노드가 방문하지 않은 곳이라면 dfs 재귀를 depth+1로 재호출
3. 이미 방문한 노드라면 맵에 저장된 노드의 depth를 얻어내어 다른곳으로부터 연결된 뎁스값과 비교 진행. 현재 순회중인 뎁스가 더 큰 경우 맵을 재호출한다

#include<bits/stdc++.h>
using namespace std;
vector<int> a[10000];
int visited[10000];
int leaf[10000];
int n, m;

// 뎁스를 조사하는게 아니라 자식노드 갯수를 저장.
// visited에 저장
int dfs(int here){
    visited[here] = 1;

    for (int there : a[here]){
        if(visited[there]){
            visited[here] += visited[there];
            continue;
        }
        visited[here] += dfs(there);
    }
    return visited[here];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        int here, there;
        cin >> there >> here;

        a[here].push_back(there);
    }
    for (int i = 1; i <= n; i++){
        dfs(i);
    }

    int mx = visited[1];
    vector<int> mxIndex;

    for (int i = 1; i <= n; i++){
        if(mx < visited[i]){
            mxIndex.clear();
            mxIndex.push_back(i);
        }else if(mx == visited[i]){
            mxIndex.push_back(i);
        }

        mx = max(mx, visited[i]);
    }

    for(int idx : mxIndex){
        cout << idx << " ";
    }
    cout << "\n";

    return 0;
}

1. 로직 재개선 - 여전히 시간초과 발생
2. 로직 자체는 사실상 정답에 가까운 것 같음. 노드마다 순회를 진행하며 방문하지 않은 노드는 DFS를 진행하여 visited에 자식노드 갯수를 저장한다.
3. 반례 - 노드가 서로 순환참조를 하는 경우 무한루프에 빠지게 된다.
   • visited는 방문의 목적으로만 사용하도록 하자.