• Home
  • About
    • Jiwon Jeong photo

      Jiwon Jeong

      끊임없이 배우며 성장하는 엔지니어

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • All Categories
  • Projects

위상정렬 기본뼈대 문제

21 May 2021

Reading time ~1 minute

줄 세우기 (백준)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> graph[32001];
int inDegree[32001]; 
int N, M;
 
void TopologicalSort(void){
    queue<int> q;
    
    for(int i = 1; i <= N; i++)
        if(!inDegree[i])
            q.push(i); // 진입차수가 0인 노드를 큐에 삽입
        
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        cout << cur << ' '; //큐에서 빠져나오는 순서가 출력순서
        for(int i = 0; i < graph[cur].size(); i++){
            inDegree[graph[cur][i]]--;
            if(!inDegree[graph[cur][i]]) // 새롭게 진입차수가 0인 노드를 큐에 삽입
                q.push(graph[cur][i]);
        }
    }
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        inDegree[b]++;
    }
    
    TopologicalSort();
    
    return 0;
}


Algorithm Share Tweet +1