줄 세우기 - 2252

//2252 - 줄 세우기                                                                                                   
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<vector<int>> adj;
vector<int> order;
vector<bool> seen;
 
void init()
{
    cin >> N >> M;
    adj = vector<vector<int>>(N+1);
    seen = vector<bool>(N+1, false);
    int u, v;
    for(int i = 0; i<M; ++i)
    {
        cin >> u >> v;
        adj[v].push_back(u);
    }
 
}
 
void dfs(int here)
{
    seen[here] = true;
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i];
        if(!seen[there])
            dfs(there);
    }
    order.push_back(here);
}
 
void topologicalSort()
{
    for(int i = 1; i<=N; ++i)
        if(!seen[i])
            dfs(i);
    for(int i = 0; i<N; ++i)
        cout << order[i] << " ";
}
 
int main()
{
    init();
    topologicalSort();
}

 

 

 

 

 

 

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

2252번: 줄 세우기

 

 

 

 

 

 

줄 세우기

위상정렬 문제

DAG가 아닌 입력이 없어 싸이클이 생기는 경우를 골라내는 부분은 넣지 않았습니다.