[PS] BOJ 2252 줄세우기

BOJ-2252 줄 세우기

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

본 문제는 단순히 입력을 인접리스트인 그래프로 만든뒤에, 위상정렬한 결과를 출력하면 된다. solution

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#define ALL(C)  (C).begin(),(C).end()
using namespace std;  
int N, M;  
vector<pair<list<int>,bool> > G;  //first(key), second(visit)  
list<int> tlist;  
void DFS(int v) {  
    G[v].second = true;
    for_each(ALL(G[v].first), [](int& elem)->void{
        if (!G[elem].second){
            DFS(elem);
        }
    });
    tlist.push_front(v);
}
void TopoLogicalSort() {  
    tlist.clear();
    for (int i = 0; i < G.size(); i++){
        if (!G[i].second){
            DFS(i);
        }
    }
}
int main() {  
    cin >> N >> M;
    G.assign(N, pair<list<int>,bool>());
    for (int i = 0; i < M; i++){
        int A, B;
        cin >> A >> B;
        G[A-1].first.push_back(B-1);
        G[A-1].second = false;
    }
    TogoLogicalSort();
    for_each(ALL(tlist), [](int& elem)->void{cout << elem+1 << ' '; });
    return 0;
}
Copyright (C) 2016 (KimBom) all rights reserved.