문제

문제 링크

해설

• ‘트리도 그래프의 일종이다’ 라는 개념을 머릿속에 꼭 넣어둡시다.
• 따라서 트리를 연결리스트로 취급해서 DFS로 리프노드를 찾아내면 쉽게 풀 수 있습니다.
• 이 문제에서 숨겨져있는 함정은 사이클이 존재할 수도 있다는 점입니다.
  • 예를 들어 A가 B를 신뢰하고, B가 A를 신뢰한다면
  • 연결리스트로 구현한 저희 코드상으로는 A와 B 사이에 양방햔 간선이 만들어지고 하나의 사이클이 만들어집니다.
  • 이 상태에서 DFS를 수행하면 무한 loop를 도므로 반드시 visited 플래그로 방문여부를 check 해야만 합니다!

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool visited[10'001];

int dfs(const vector<vector<int>>& comp, int n) {
    int ret = 1;
    visited[n] = true;    // 사이클 방지해야 합니다.
    for (auto i : comp[n])
        if (!visited[i]) ret += dfs(comp, i);
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int N, M;
    cin >> N >> M;

    vector<vector<int>> computers(N + 1);
    for (int i = 0; i < M; i++) {
        int s, e;
        cin >> s >> e;
        computers[e].push_back(s);
    }
    int max_computers = 0;
    vector<int> answers(N + 1);
    for (int i = 1; i <= N; i++) {
        answers[i] = dfs(computers, i);
        max_computers = max(max_computers, answers[i]);
        memset(visited, false, sizeof(visited));
    }
    for (int i = 1; i <= N; i++)
        if (answers[i] == max_computers) cout << i << ' ';
    return 0;
}

소스코드 링크

결과