백준 2252 줄 세우기 혼내주기

 

위상정렬 문제.
키 작은 학생 -> 키 큰 학생 방향으로 edge를 더하고, 자신보다 키가 더 작은 비교 결과?가 없는 학생들마다 postorder로 출력하면 된다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

vector<int> innode[32001];
bool visited[32001], isNode[32001];
int n, m;

void input() {
    fastio;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int a, b; cin >> a >> b;
        isNode[a] = true;
        innode[b].push_back(a);
    }
}

void print(int u) {
    if(visited[u]) return;
    visited[u] = true;

    for(int v : innode[u]) 
        print(v);
    
    cout << u << " ";
}

int main() {
    input();

    for(int i = 1; i <= n; ++i) 
        if(!isNode[i]) 
            print(i);
}