[백준 2252] 줄 세우기(C++)

https://www.acmicpc.net/problem/2252

위상 정렬과 무슨 관계가 있는지는 모르겠지만 dequeue로 풀 수 있을 것 같아서 풀어봤다.

학생 A, B가 배열에 들어가있는 경우를 나누어서 앞 혹은 뒤에 값을 추가해주었다.

1) A, B가 모두 배열에 없을 경우

A와 B 모두 deque에 순서대로 삽입

2) A만 배열에 없는 경우

A는 B의 앞에 있어야하므로 A를 앞에 삽입

3)B만 배열에 없는 경우

B는 A의 뒤에 있어야하므로 B를 뒤에 삽입

이걸로 끝인줄 알았지만 마지막으로 주어지지 않은 학생들의 번호를 아무대나 넣어주면 끝이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    deque<int> deck;
    vector<bool> visit(n+1, 0);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        if(!visit[x]&&!visit[y]){
            deck.push_back(x);
            deck.push_back(y);
            visit[x] = true;
            visit[y] = true;
        } else if(!visit[x]){
            deck.push_front(x);
            visit[x] = true;
        } else if(!visit[y]){
            deck.push_back(y);
            visit[y] = true;
        }
    }
    for(int i=1; i<=n; i++){
        if(!visit[i]){
            deck.push_back(i);
        }
    }
    while(!deck.empty()){
        cout << deck.front() << ' ';
        deck.pop_front();
    }
    cout << endl;
    return 0;
}