• Home
  • About
    • Dochoi의 소소한 코딩 모음 photo

      Dochoi의 소소한 코딩 모음

      코딩을 하면서 느낀점들을 모은 공간입니다.

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • AI
    • Algorithm
    • Algorithm-Test
    • Cloud
    • Docker
    • Kubernetes
    • iOS
    • Culture
  • Projects

[백준]:1766(문제집)

28 Oct 2020

Reading time ~1 minute

algorithm-test

1766(문제집)

//
//  main.cpp
//  algorithmtest
//
//  Created by 최동규 on 2020/09/13.
//  Copyright © 2020 최동규. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

vector<int> v[32000];
int check[32000];
int main(int argc, const char * argv[]) {
    // insert code here...
 //   freopen("input", "r", stdin);
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        check[b] += 1;
    }
    priority_queue<int> pq;
    for (int i = 0 ; i < n; i++)
    {
        if (check[i] == 0)
            pq.push(-i);
    }
    
   
    while(!pq.empty())
    {
        int node = -pq.top();
        pq.pop();
        cout << node + 1 << " ";
        check[node] = -1;
        for (int j = 0; j < v[node].size() ;j++)
        {
            check[v[node][j]] -= 1;
            if (check[v[node][j]] == 0)
                pq.push(-v[node][j]);
        }
    }

    return 0;
}

고찰

기업코딩 테스트에서 종종 위상정렬이 나와서 위상정렬을 연습한 문제입니다



Algorithm-TestTopological Sort Share Tweet +1