본문으로 바로가기

위상 정렬을 통해 문제를 풀 수 있다.

#include <cstdio>
#include <vector>
using namespace std;

vector<vector<int>> v;
vector<int> topology;
int n, m;

int main() {
  scanf("%d %d", &n, &m);
  v.resize(n+1);
  topology.resize(n+1);
  int x, y;
  while (m--) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    topology[y]++;
  }
  for (int i=1; i<=n; i++) {
    for (int j=1; j<=n; j++) {
      if (topology[j] == 0) {
        printf("%d ", j);
        for (auto e: v[j]) {
          topology[e]--;
        }// j 뒤에 오는 데이터의 위상을 감소시킨다
        topology[j]--;// 위상을 -1로 만들어 데이터가 이미 사용되었음을 나타낸다
        break;
      }// j의 위상이 0이라면
    }
  }// 위상 정렬
  return 0;
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 1789: 수들의 합  (0) 2018.06.19
[BOJ] 1783: 병든 나이트  (0) 2018.06.19
[BOJ] 1766: 문제집  (0) 2018.06.18
[BOJ] 1735: 분수합  (0) 2018.06.18
[BOJ] 1712: 손익분기점  (0) 2018.06.18
[BOJ] 1655: 가운데를 말해요  (0) 2018.06.18

댓글을 달아 주세요