[백준(Baekjoon)][자바(java)] 3665 : 최종 순위 / 위상 정렬

 

https://www.acmicpc.net/problem/3665

3665번: 최종 순위

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int t = Integer.parseInt(br.readLine()), n, m, i, j, rank[], u, v, cnt;
		List<List<Integer>> edge_out; List<Integer> edges;
		int degree_in[];
		Queue<Integer> top;
		StringBuilder sb = new StringBuilder(), sb2;
		loop:
		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			rank = new int[n];
			st = new StringTokenizer(br.readLine());
			for (i = 0; i < n; ++i)
				rank[i] = Integer.parseInt(st.nextToken()) - 1;
			edge_out = new ArrayList<>();
			for (i = 0; i < n; ++i)
				edge_out.add(new ArrayList<>());
			degree_in = new int[n];
			for (i = 0; i < n - 1; ++i) {
				u = rank[i];
				edges = edge_out.get(u);
				for (j = i + 1; j < n; ++j) {
					v = rank[j];
					edges.add(v);
					degree_in[v]++;
				}
			}
			m = Integer.parseInt(br.readLine());
			for (i = 0; i < m; ++i) {
				st = new StringTokenizer(br.readLine());
				u = Integer.parseInt(st.nextToken()) - 1;
				v = Integer.parseInt(st.nextToken()) - 1;
				if (!edge_out.get(u).contains(v)) {
					int tmp; tmp = u; u = v; v = tmp; 
				}
				edge_out.get(u).remove((Integer) v);
				edge_out.get(v).add(u);
				degree_in[u]++;
				degree_in[v]--;
			}
			cnt = 0;
			top = new LinkedList<>();
			for (i = 0; i < n; ++i) {
				if (degree_in[i] == 0) {
					cnt++;
					if (cnt > 1) {
						sb.append("?\n");
						continue loop;
					}
					top.add(i);
				}
			}
			sb2 = new StringBuilder();
			for (i = 0; i < n; ++i) {
				if (top.isEmpty()) {
					sb.append("IMPOSSIBLE\n");
					continue loop;
				}
				u = top.remove();
				sb2.append((u + 1) + " ");
				for (int vv : edge_out.get(u)) {
					degree_in[vv]--;
					if (degree_in[vv] == 0)
						top.add(vv);
				}
			}
			sb.append(sb2.toString() + "\n");
		}
		br.close();
		System.out.println(sb.toString());
	}
}