최종순위

 

*위상정렬

*isPrev[][] 작년 등수가 더 높은 팀이 앞에 온 경우 (-1) / 뒤에 온 경우 (1) -> compareTo 의 반환값과 동일 

*등수에 변화가 있으면 작년 등수가 더 높은 팀의 위상 배열을 ++ / 낮은 팀은 위상 배열을 -- 하여 등수에 변화를 준다. 

#include <iostream> #include <vector> #include <queue> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n, m; cin >> n; int prev[501] = { 0 }; for (int i = 1; i <= n; i++) { //작년 등수 cin >> prev[i]; } int isPrev[501][501] = { {0} }; int indegree[501] = { 0 }; for (int i = 1; i <= n; i++) { int a = prev[i]; for (int j = 1; j <= i; j++) { if (i == j) continue; int b = prev[j]; isPrev[a][b] = 1; //더 등수가 높은 것을 앞에 둔다. isPrev[b][a] = -1; indegree[a]++; } } cin >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; //a가 더 빠르면 if (isPrev[a][b] < 0) { indegree[a]++; indegree[b]--; } else { indegree[a]--; indegree[b]++; } isPrev[a][b] = -isPrev[a][b]; isPrev[b][a] = -isPrev[b][a]; } queue<int> q; bool visited[501] = { 0 }; int res[501] = { 0 }, idx = 0; for (int i = 1; i <= n; i++) { if (indegree[prev[i]] == 0) { q.push(i); } } while (!q.empty()) { int now = q.front(); q.pop(); res[++idx] = prev[now]; visited[now] = true; for (int i = 1; i <= n; i++) { if (!visited[i]) { indegree[prev[i]]--; if (!indegree[prev[i]]) { q.push(i); } } } } if (idx < n) { cout << "IMPOSSIBLE" << '\n'; continue; } for (int i = 1; i <= n; i++) { cout << res[i] << ' '; } cout << '\n'; } return 0; }