[Graph] BOJ 1766 문제집

문제 링크 : www.acmicpc.net/problem/1766

1766번: 문제집

문제의 조건을 잘 살펴보자.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

 

제시된 조건들을 봤을 때 문제집의 문제 간에는 선행 관계가 존재함을 알 수 있으며,

따라서 이 문제는 사이클이 없는 방향 그래프 내에서 위상 정렬의 결과를 출력하는 문제임을 캐치할 수 있다.

 

일반적인 위상 정렬은 여러 개의 결과를 낼 수 있지만,

이 문제의 경우 3번 조건에서 위상 정렬의 결과가 여러개 존재할 수 있다면 더 낮은 번호의 문제를 먼저 풀어야 하기 때문에, 단 하나의 결과만을 낼 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <string>
 
using namespace std;
typedef pair<int, int> p;
typedef struct {
    int num, indegree = 0;
}node;
 
int n, m;
node nodes[32001];
vector<int> adj[32001], order;
 
void bfs() {
    priority_queue<int> pque;
    for (int i = 1; i <= n; i++) {
        if (nodes[i].indegree == 0) pque.push(-i);
    }
 
    while (!pque.empty()) {
        int cur = -pque.top();
        pque.pop();
 
        order.push_back(cur);
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int nextnode = adj[cur][i];
            nodes[nextnode].indegree--;
            if (nodes[nextnode].indegree == 0) {
                pque.push(-nextnode);
            }
        }
    }
}
 
void init() {
    int a, b;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) nodes[i].num = i;
 
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        nodes[b].indegree++;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    bfs();
 
    for (int i = 0; i < order.size(); i++) printf("%d ", order[i]);
    printf("\n");
 
    //system("PAUSE");
    return 0;
}