백준 17616 등수 찾기

문제 링크

처음에 위상 정렬 문제인가 했는데 아니다. 1번 노드가 2번 노드보다 크다고 하더라고 1번 노드와 2번 노드 사이에 다른 노드가 올 수 있기 때문이다.

이 문제는 특정 노드의 최소 등수와 최대 등수를 구해야 하므로 특정 노드보다 확실히 큰 노드의 수와 확실히 작은 노드의 수를 구해야 한다. 고로 BFS를 2번 돌리면 된다.

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

int N, M, X;
vector<vector<int>> fwd(100001);
vector<vector<int>> rvs(100001);
bool visited[100001];

int bfs(vector<vector<int>> &graph, int start) {
    fill(visited, visited + N + 1, false); // visited 초기화
    queue<int> q;
    int cnt = 0;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cnt++;

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return cnt;
}

int main() {
    cin >> N >> M >> X;

    for (int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        fwd[from].push_back(to); // 정방향 그래프
        rvs[to].push_back(from); // 역방향 그래프
    }

    int nextCnt = bfs(fwd, X);
    int prevCnt = bfs(rvs, X);

    int U = prevCnt;         
    int V = N - nextCnt + 1; 
    cout << U << " " << V << endl;

    return 0;
}