BOJ)2252 줄 세우기

문제: icpc.me/2252

N명이 학생이 주어지고 두 학생의 키를 비교한 M개의 정보가 주어질 때 줄을 세운 결과를 출력하는 문제이다.

우리는 두 학생의 우선관계를 방향 그래프를 이용하여 설정해준 뒤 topology를 구해주면 된다.

즉 DFS를 돌리면서 먼저 끝나는 순서대로 스택에 저장해준 뒤 하나씩 뽑으면서 출력해주면 답을 얻을 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define MAX_N 32000
using namespace std;
vector<vector<int>> vt;
stack<int> st;
int n, m, x, y, visited[MAX_N + 1];
void dfs(int v) {
    visited[v] = true;
    for (auto i : vt[v]) {
        if (visited[i])
            continue;
        dfs(i);
    }
    st.push(v);
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &x, &y);
        vt[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            dfs(i);
    }
    while (st.size()) {
        printf("%d ", st.top());
        st.pop();
    }
    return 0;
}