위상정렬로 문제풀기

※우선순위 큐를 이용한 위상정렬의 방법※

1.모든 일의 선행 필요조건 관계를 따라 그래프를 그린다.

(방향 그래프 완성)

2. 각 일에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)

3. indegree가 0인 일을 모두 찾아 우선순위 큐에 넣는다

4. 우선순위 큐에서 일 하나를 꺼낸다.

(위상정렬의 결과 출력을 위해 이때 꺼내진 일을 출력하면 된다.)

5. 방금 꺼낸 일에 연결된 모든 일들의 indegree를 1씩 감소시킨다.

6. indegree가 감소된 일들 중 indegree가 0인 일이 있으면 우선순위 큐에 넣어준다.

7. 우선순위 큐가 빌 때까지 4~6을 반복한다.

※bfs와 dfs를 이용한 위상정렬의 방법※

공통적으로 먼저 사이클이 있는지 없는지를 판단해야 위상정렬이 생기게 된다.

하지만 위상정렬의 사이클 여부는 위상정렬 후 만든 후 검사 할 수 있다.

★bsf를 통한 구현★ (우선순위 큐와 유사)

1) indegree(진입차수) 가 0인 점을 큐에 넣고 탐색을 시작한다.

2) 현재점과 연결된 정점의 진입차수를 1 감소시킨다.

3) 그 중 진입차수가 0이 되는 점을 큐에 넣고 반복

-> 진입차수가 0인 점을 넣는 순서가 위상정렬의 순서이다.

★dsf를 통한 구현★

dfs의 재귀를 탈출하는 곳은 이 정점과 연결된 점을 이미 전부 방문한 뒤 이므로

-> 재귀를 탈출 할 때 마다 넣어두고 최종 결과를 뒤집어 주면 위상정렬한 상태가 나온다.

// 줄세우기 [백준]2252번

//bsf를 통한 구현

#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
int n, m, a, b;
vector<vector<int> > graph;
int indegree[32123];
vector<int> ans;
 
void bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) { // 현재 진입차수가 0인 점을 큐에 넣음
            q.push(i);
            ans.push_back(i);
        }
    }
 
    while (!q.empty()) {
        int here = q.front();
        q.pop();
 
        for (int i = 0; i<graph[here].size(); i++) {
            int there = graph[here][i];
            indegree[there]--; // 연결된 곳의 차수를 1씩 감소해준다.
            if (indegree[there] == 0) {  // 다시 0인 곳을 큐에 넣음
                q.push(there);
                ans.push_back(there);
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    graph.resize(n + 1);
    for (int i = 0; i<m; i++) {
        scanf("%d %d", &a, &b);
        graph[a].push_back(b); // a가 b앞에 와야 한다.
        indegree[b]++; // b의 진입차수 증가
    }
 
    bfs();
 
    for (int i = 0; i<ans.size(); i++) 
        printf("%d ", ans[i]);
    return 0;
}

//dfs를 통한 구현

#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n, m, a, b;
vector<vector<int> > graph;
bool visited[32123];
vector<int> ans;
 
void dfs(int here)
{
    if (visited[here]) return;
    visited[here] = true;
 
    for (int i = 0; i<graph[here].size(); i++) {
        int there = graph[here][i];
        dfs(there);
    }
 
    ans.push_back(here); // 재귀 탈출 하면서 현재 정점을 넣어준다.
}
 
int main()
{
    scanf("%d %d", &n, &m);
    graph.resize(n + 1);
    for (int i = 0; i<m; i++) {
        scanf("%d %d", &a, &b);
        graph[a].push_back(b); // a가 b앞에 와야 한다.
    }
 
    for (int i = 1; i <= n; i++)
        dfs(i);
 
    reverse(ans.begin(), ans.end()); // 결과를 뒤집어 준다.
    for (int i = 0; i<ans.size(); i++) printf("%d ", ans[i]);

    return 0;
}