BOJ 3665: 최종 순위 작성일 2020-02-25 https://www.acmicpc.net/problem/3665 2월동안 187문제 풀기(지난달 누적 87개) (66/187) 위상정렬 문제 그래프에서 위상정렬이 안되는 경우는 사이클이 생기는 경우이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h> using namespace std; int main() { int TC, N, M, a, b; scanf("%d", &TC); while (TC--) { scanf("%d", &N); vector<vector<int>> adj(N+1, vector<int>(N+1)); vector<int> arr(N), indegree(N+1); for(int i = 0; i < N; i++) scanf("%d", &arr[i]); for(int i = 0; i < N; i++) for(int j = i+1; j < N; j++) adj[arr[i]][arr[j]] = 1; scanf("%d", &M); for(int i = 0; i < M; i++) { scanf("%d %d", &a, &b); swap(adj[a][b], adj[b][a]); } for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(adj[i][j]) indegree[j]++; queue<int> q; for(int i = 1; i <= N; i++) if(indegree[i] == 0) q.push(i); bool flag = !q.empty(); int cnt = 0; vector<int> ans; ans.reserve(N); while(q.size()) { cnt++; if(q.size() != 1) { flag = false; break; } int cur = q.front(); ans.push_back(q.front()); q.pop(); for(int i = 1; i <= N; i++) { if(adj[cur][i]) { if(--indegree[i] == 0) q.push(i); } } } if(!flag || cnt != N) { printf("IMPOSSIBLE\n"); } else { for(int i : ans) printf("%d ", i); printf("\n"); } } }