(3665) 최종 순위

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

단계별로 풀어보기

28단계(위상 정렬) 2번째

 

 

 

처음에 작년 순위를 알려주는 것은 모든 팀에 대한 간선 n(n-1)/2개가 있다는 것이다. 여기서 상대 순위가 바뀐 모든 팀을 알려주므로, 해당 팀에 대해 간선 방향을 바꾸면 된다. 이때 간선의 개수는 바뀌지 않는다.

이를 이용해 위상 정렬 알고리즘을 쓰면 되지만, 이 문제는 그래프가 특수한 형태이기 때문에 다른 방법으로 풀 수도 있다.

1등 팀을 그래프에서 제거하면 1등 팀은 2~n등 팀 전부와 간선이 이어져 있었으므로 n-1개의 간선이 제거되고, 진입 차수가 0인 정점은 2등 팀이 된다. 마찬가지로 2등 팀을 제거하면 3~n등 팀 n-2개의 간선이 제거되고 3등 팀이 큐에 들어가게 된다.

즉 각 정점은 진입 차수가 0~n-1개로 이루어져 있으며, 이를 정렬하면 위상 정렬 순서가 된다. 만약 0~n-1개가 한 번씩 나오지 않는다면 잘못된 정보가 들어온 경우이므로 IMPOSSIBLE을 출력하면 된다. 모든 두 정점에 대해 간선이 있으므로 확실한 순위를 만들 수 없는 경우는 존재하지 않는다. 다시 말해 ?는 출력할 일 없는 함정이다.

 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

void solve(){
  int n, m;
  
  cin >> n;
  
  vector<int> rank(n), indegree(n+1);
  vector adj(n+1, vector<bool> (n+1));
  
  for(int i=0;i<n;i++)  cin >> rank[i];
  
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      adj[rank[i]][rank[j]]= true;
    }
  }
  
  cin >> m;
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    if(adj[a][b]){
      adj[a][b]= false;
      adj[b][a]= true;
    }else{
      adj[b][a]= false;
      adj[a][b]= true;
    }
  }
  
  for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      if(adj[i][j])  indegree[j]++;
      else  indegree[i]++;
    }
  }
  
  vector<pair<int,int>> v;
  
  for(int i=1;i<=n;i++)  v.push_back({indegree[i], i});
  
  sort(v.begin(), v.end());
  
  for(int i=0;i<n;i++){
    if(v[i].first!=i){
      cout << "IMPOSSIBLE\n";
      return;
    }
  }
  
  for(auto elem:v)  cout << elem.second << " ";
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }
  
  return 0;
}