Baekjoon Online Judge

algorithm practice

-問題を逐次解く

35.位相整列

次に、反転しないように方向性のあるグラフィック頂点をリストするアルゴリズムについて説明します.

2.最終順位

3665番
幹線を直接定義して位相位置合わせを行う問題

今回の問題は、昨年のランキングに対してすべてのチームのリストを指定すれば、今年のランキングのプログラムを作成することができるということです.△しかし、本部が発表した情報に基づいて今年の正確な順位を決めることができない可能性もあるし、一致しない誤った情報である可能性もある.この2つの状況を見出す必要がある.
位相整列は一般にAがBより前の場合であり,この場合は単純に関係を見ればよい.しかし今回の問題は,あらかじめ順序を決めておき,順序の前後関係が変わる場合であるため,少し複雑な位相ソート問題といえる.したがって,今回の問題については順位に応じてすべての関係を追加する.
変更された順位に対して、エッジの方向を変更し、位相ソートを行います.同じインバウンド回数で順番を区別できない場合は「?」データが一致しないため並べ替えができない場合は、「IMPOSIBLE」を出力します.
Java/Python

Java

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[] indegree;
	static boolean[][] edges;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			N = Integer.parseInt(br.readLine());
			indegree = new int[N + 1];
			edges = new boolean[N + 1][N + 1];

			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				int num = Integer.parseInt(st.nextToken());
				indegree[num] = i;

				for (int j = 1; j <= N; j++) {
					if (j != num && !edges[j][num])
						edges[num][j] = true;
				}
			}

			int M = Integer.parseInt(br.readLine());
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int n1 = Integer.parseInt(st.nextToken());
				int n2 = Integer.parseInt(st.nextToken());
				swap(n1, n2);
			}
			bw.write(topologicalSort() + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static String topologicalSort() {
		Queue<Integer> queue = new LinkedList<>();
		StringBuilder sb = new StringBuilder();

		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0)
				queue.offer(i);
		}

		for (int i = 1; i <= N; i++) { // 정점 개수만큼 반복
			if (queue.size() == 0)
				return "IMPOSSIBLE";
			if (queue.size() > 1)
				return "?";
			int cur = queue.poll();
			sb.append(cur + " ");

			for (int j = 1; j <= N; j++) {
				if (edges[cur][j]) {
					edges[cur][j] = false;
					if (--indegree[j] == 0)
						queue.offer(j);
				}
			}
		}
		return sb.toString();
	}

	private static void swap(int n1, int n2) {
		if (edges[n1][n2]) {
			edges[n1][n2] = false;
			edges[n2][n1] = true;
			indegree[n1]++;
			indegree[n2]--;

		} else {
			edges[n1][n2] = true;
			edges[n2][n1] = false;
			indegree[n1]--;
			indegree[n2]++;
		}
	}
}

Python

import sys
from collections import deque

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    rank = list(map(int, sys.stdin.readline().split()))
    edges = [[False]*(n+1) for _ in range(n + 1)]
    indegree = [0] * (n + 1)
    
    for i in range(n):
        for j in range(i + 1, n):
            edges[rank[i]][rank[j]] = True
            
    m = int(sys.stdin.readline())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        edges[a][b], edges[b][a] = edges[b][a], edges[a][b]

    que = deque()
    answer = []
    cnt = 0
    for i in range(1, n + 1):
        indegree[i] = edges[i].count(True)
        if indegree[i] == 0:
            cnt += 1
            que.append(i)

    if cnt != 1:
        if cnt > 1:
            print("?")
        elif cnt == 0:
            print("IMPOSSIBLE")
        continue
            
    while que and cnt == 1:
        cnt = 0
        cur = que.popleft()
        answer.append(cur)
        for i in range(1, n + 1):
            if edges[i][cur]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    cnt += 1
                    que.append(i)
                    
    if cnt > 1:
        print("?")
    elif len(answer) != n:
        print("IMPOSSIBLE")
    else:
        print(*answer[::-1])