219. 최종 순위

백준

1. 위상 정렬

from collections import deque

for t in range(int(input())):
  n = int(input())
  indegree = [0] * (n + 1)
  graph = [[False] * (n + 1) for i in range(n + 1)]

  #작년 순위 정보 입력
  data = list(map(int, input().split())
  )
  #방향 그래프의 간선 정보 초기화
  for i in range(n):
    for j in range(i + 1, n): #자기보다 낮은 순위에 간선 추가
      graph[data[i]][data[j]] = True
      indegree[data[j]] += 1

  #올해 변경된 순위 정보 입력
  m = int(input())
  for i in range(m):
    a, b = map(int, input().split())
    #간선의 방향 뒤집기
    if graph[a][b]:
      graph[a][b] = False
      graph[b][a] = True
      indegree[a] += 1
      indegree[b] -= 1
    else:
      graph[a][b] = True
      graph[b][a] = False
      indegree[a] -= 1
      indegree[b] += 1

  #위상정렬 시작
  result = []
  q = deque()
  
  for i in range(1, n + 1):
    if indegree[i] == 0:
      q.append(i)
  
  certain = True #위상 정렬 결과 하나인지 여부
  cycle = False #그래프 내 사이클 존재 여부

  for i in range(n):
    if len(q) == 0: #큐가 비어있다면 사이클 발생
      cycle = True
      break
    
    if len(q) >= 2: #큐에 원소가 2개 이상이라면 가능한 정렬 결과가 여러개라는 의미
      certain = False
      break
    
    now = q.popleft()
    result.append(now)
    for j in range(1, n + 1):
      if graph[now][j]:
        indegree[j] -= 1
        if indegree[j] == 0:
          q.append(j)

  if cycle:
    print("IMPOSSIBLE")
  elif not certain:
    print("?")
  else:
    for i in result:
      print(i, end=' ')
    print()

2. C++

#include <bits/stdc++.h>

using namespace std;

int testCase, n, m;
// 모든 노드에 대한 진입차수는 0으로 초기화
int indegree[501];
// 각 노드에 연결된 간선 정보를 담기 위한 배열 초기화
bool graph[501][501];

int main(void) {
    cin >> testCase;

    // 테스트 케이스(Test Case)만큼 반복
    for (int tc = 0; tc < testCase; tc++) {
        fill(indegree, indegree + 501, 0);
        for (int i = 0; i < 501; i++) {
            fill(graph[i], graph[i] + 501, false);
        }

        cin >> n;
        // 작년 순위 정보 입력
        vector<int> v;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            v.push_back(x);
        }
        // 방향 그래프의 간선 정보 초기화
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                graph[v[i]][v[j]] = true;
                indegree[v[j]] += 1;
            }
        }

        // 올해 변경된 순위 정보 입력
        cin >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            // 간선의 방향 뒤집기
            if (graph[a][b]) {
                graph[a][b] = false;
                graph[b][a] = true;
                indegree[a] += 1;
                indegree[b] -= 1;
            }
            else {
                graph[a][b] = true;
                graph[b][a] = false;
                indegree[a] -= 1;
                indegree[b] += 1;
            }
        }

        // 위상 정렬(Topology Sort) 시작
        vector<int> result; // 알고리즘 수행 결과를 담을 리스트
        queue<int> q; // 큐 라이브러리 사용

        // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        bool certain = true; // 위상 정렬 결과가 오직 하나인지의 여부
        bool cycle = false; // 그래프 내 사이클이 존재하는지 여부

        // 정확히 노드의 개수만큼 반복
        for (int i = 0; i < n; i++) {
            // 큐가 비어 있다면 사이클이 발생했다는 의미
            if (q.size() == 0) {
                cycle = true;
                break;
            }
            // 큐의 원소가 2개 이상이라면 가능한 정렬 결과가 여러 개라는 의미
            if (q.size() >= 2) {
                certain = false;
                break;
            }
            // 큐에서 원소 꺼내기
            int now = q.front();
            q.pop();
            result.push_back(now);
            // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for (int j = 1; j <= n; j++) {
                if (graph[now][j]) {
                    indegree[j] -= 1;
                    // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                    if (indegree[j] == 0) {
                        q.push(j);
                    }
                }
            }
        }

        // 사이클이 발생하는 경우(일관성이 없는 경우)
        if (cycle) cout << "IMPOSSIBLE" << '\n';
        // 위상 정렬 결과가 여러 개인 경우
        else if (!certain) cout << "?" << '\n';
        // 위상 정렬을 수행한 결과 출력
        else {
            for (int i = 0; i < result.size(); i++) {
                cout << result[i] << ' ';
            }
            cout << '\n';
        }
    }