[위상 정렬] BOJ 3665 최종 순위

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

3665번: 최종 순위

 

문제 해결 알고리즘

 

위상 정렬문제인데 인접리스트를 이중배열로 구현해야한다는 점과 "?"과 "impossible"을 구분해주어야하는 점이 어려웠다. (두 팀의 순서를 바꿀 때 좀 복잡하기 때문에 이중배열이 더 편했다.)

 

q에 원소가 2개 이상이면 "?"를 출력해주고

 

q에 원소가 없고 방문하지 않은 노드가 있다면 "impossible"을 출력해준다.

 

2개 이상도 아니고 모든 노드를 방문했다면 순서를 출력해준다.

 

https://kimmessi.tistory.com/207

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int indegree[501];
bool graph[501][501], visited[501];
vector<int> result;
int n; 
bool flag1 = false;

void topologySort(){
    queue<int> q;

    for(int i=1;i<=n;i++){
        if(indegree[i] == 0){
            q.push(i);
            visited[i] = true;
        }
    }

    while(!q.empty()){

        if(q.size() > 1) {
           flag1 = true;
            return;
        }

        int now = q.front();

        q.pop();

        result.push_back(now);

        for(int i=1;i<501;i++){
            if(graph[now][i] == true){
                indegree[i] --;

                if(indegree[i] == 0){
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T; cin >> T;

    while(T--){
        cin >> n;
        vector<int> v(n);

        for(int i=0;i<n;i++) cin >> v[i];

        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                graph[v[i]][v[j]] = true;
                indegree[v[j]]++;
            }
        }

        int m; cin >> m;

        for(int i=0;i<m;i++){
            int a, b; cin >> a >> b;

            if(graph[a][b]){
                graph[a][b] = false;
                graph[b][a] = true;
                indegree[b]--; indegree[a]++;
            }
            else if(graph[b][a]){
                graph[b][a] = false;
                graph[a][b] = true;
                indegree[b]++; indegree[a]--;
            }
        }
        
        topologySort();

        bool flag = true;
        for(int i=1;i<=n;i++){
            if(!visited[i]) flag = false;
        }

        if(flag1){
            cout << "?";
        }else if(flag){
            for(int i=0;i<n;i++){
                cout << result[i] << ' ';
            }
        }
        else cout << "IMPOSSIBLE";

        cout << "\n";

        for(int i=0;i<501;i++){
            indegree[i] = 0;
            visited[i] = false;
            for(int j=0;j<501;j++){
                graph[i][j] = false;
            }
        }
        result.clear();
        flag1 = false;
    }
}