최종 순위 - 3665

//3665 - 최종 순위
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int arr[501];
int idx[501];
int adj[501][501];
vector<bool> visit;
 
void init()
{
    cin >> N;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            adj[i][j] = 0;
    visit = vector<bool>(N + 1, false);
    for (int i = 1; i <= N; ++i)
        cin >> arr[i], idx[arr[i]] = i;
    for (int i = 1; i < N; ++i)
        for (int j = i + 1; j <= N; ++j)
            adj[i][j] = 1;
    cin >> M;
    int x, y;
    for (int i = 0; i < M; ++i)
    {
        cin >> x >> y;
        x = idx[x];
        y = idx[y];
        if (adj[x][y])
            adj[x][y] = 0, adj[y][x] = 1;
        else if(adj[y][x])
            adj[y][x] = 0, adj[x][y] = 1;
    }
}
 
void dfs(vector<int> &order, int here)
{
    visit[here] = true;
    for (int there = 1; there <= N; ++there)
        if (adj[here][there] && !visit[there])
            dfs(order, there);
    order.push_back(here);
}
 
void topologicalSort()
{
    vector<int> order;
    for (int i = 1; i <= N; ++i)
        if (!visit[i])
            dfs(order, i);
 
    for (int i = N - 1; i > 0; --i)
        for (int j = i - 1; j >= 0; --j)
            if (adj[order[j]][order[i]])
            {
                cout << "IMPOSSIBLE"
                     << "\n";
                return;
            }
 
    for (int i = N - 1; i >= 0; --i)
        cout << arr[order[i]] << " ";
    cout << "\n";
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int C;
    cin >> C;
    for (int tn = 0; tn < C; ++tn)
    {
        init();
        topologicalSort();
    }
}

 

 

 

 

 

 

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

3665번: 최종 순위

 

 

 

 

 

 

최종 순위

위상정렬 문제입니다.

몇몇 팀의 순위가 바뀌었을때, 바뀐 순위대로 출력해주면 됩니다.

맨 처음 주어진 순위를 단방향 그래프로 만든후, 

순위가 바뀐 팀들이 주어질때, 해당 팀을 나타내는 노드 사이에 연결된 간선의 방향을 바꿔준다음 위상정렬 알고리즘을 이용하면 됩니다.

DAG라면 바뀐 순위를 출력할수 있고, 싸이클이 있다면 IMPOSSIBLE을 출력하면 됩니다.

이때 함정이 문제에서 요구하는 '?'를 출력하는 경우는 절대 발생하지 않습니다.

두 팀의 간선의 방향을 아무리 바꾼들 싸이클은 발생할수 있지만 순서가 모호해지는 위상은 나타날수 없기 때문입니다.