3665번(다시풀기)

3665번 - 최종 순위

위상정렬을 잊어버리기도 했고, 나에게 꽤나 까다로운 문제였다.

이 문제는 항상 연결리스트로 그래프 문제를 풀던 나한테, 인접 행렬로 푸는게 효과적일 수 있다는 걸 깨닫게 해줬다.

그리고 순위가 뒤바뀔 때, 우선 순위가 통째로 바뀌는 것이 아니라, indegree 값이 ++ 혹은 -- 해줘야 한다는 점이 헷갈렸다.

그리고 마지막으로 답을 구할 때, 평소처럼 while(!q.empty()) 가 아니라 N까지만 돌면서 

큐에 들어있지 않다면, 이는 DAG가 아니여서, 즉 싸이클이 생겨서 순위를 구할 수 없다는 점이고.

큐에 두개의 값이 들어있다면, 이는 순위를 정확하게 결정할 수 없기 때문에 ? 를 출력해야 했다.

생각보다 많은걸 얻은 문제인 것 같다. 다음에 또 다시 풀어봐야지

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int indegree[501];
int g[501][501];
int a[501];
void init()
{
    for (int i = 0; i < 501; i++)
    {
        a[i] = indegree[i] = 0;
        for (int j = 0; j < 501; j++)
        {
            g[i][j] = 0;
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int n, m, F=-1;
        cin >> n;
        init();
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
 
        for (int i = 1; i < n; i++)
        {
            for (int j = i+1; j <= n; j++)
            {
                g[a[i]][a[j]] = 1;
                indegree[a[j]]++;
            }
        }
 
        cin >> m;
 
        for (int i = 0; i < m; i++)
        {
            int x, y;
            cin >> x >> y;
            
            if (g[x][y] == 1)
            {
                indegree[x]++;
                indegree[y]--;
                swap(g[x][y], g[y][x]);
            }
            else if (g[y][x] == 1)
            {
                indegree[y]++;
                indegree[x]--;
                swap(g[x][y], g[y][x]);
            }
        }
 
        queue<int> q;
        queue<int> ans;
 
        for (int i = 1; i <= n; i++)
        {
            if (indegree[i] == 0)
            {
                q.push(i);
                ans.push(i);
            }
        }
 
 
        for(int i=0;i<n;i++)
        {
            if (q.size() == 0)
            {
                F = 0;
                break;
            }
 
            if (q.size() >= 2)
            {
                F = 1;
                break;
            }
 
            int here = q.front();
            q.pop();
 
            for (int i = 1; i <= n; i++)
            {
                if (g[here][i] == 1)
                {
                    indegree[i]--;
                    if (indegree[i] == 0)
                    {
                        q.push(i);
                        ans.push(i);
                    }
                }
            }
        }
 
        if (F == 0)
        {
            cout << "IMPOSSIBLE\n";
        }
        else if (F == 1)
        {
            cout << "?\n";
        }
        else
        {
            while (!ans.empty())
            {
                cout << ans.front() << " ";
                ans.pop();
            }
            cout << "\n";
        }
 
    }
    return 0;
}