[C++] 백준 3665번 : 최종 순위

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

 

 

 

 

[접근]

? : 한노드에서 진입차수를 --했을때 진입차수가 0인 노드가 2개 이상일시 순서가 불확실해진다 

-> 큐에 있는 노드의 개수가 2개 이상일 경우 ?를 출력하도록 했다. 
impossible : 사이클이 존재하는 경우 -> n과 result의 사이즈가 동일하지 않을경우에 impossible을 출력하도록 했다. 

 

 

[코드]

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


int n,m;
vector<int> r;
vector<int> map[501];

void solve(){
    queue<int> q;
    vector<int> result;
    
    bool findthing = false;
    
    for(int i=1;i<=n;i++){ 
        if(r[i]==0) q.push(i);
    }

    while(!q.empty()){
        if(q.size() > 1) {
            findthing = true;
            break;
        }
        int now = q.front();
        q.pop();
        result.push_back(now);
        
        for(int tmpmap : map[now]){
            r[tmpmap]--;
            if(r[tmpmap]==0){
                q.push(tmpmap);
            }
        }
    }
    if(findthing) cout<<"?\n";
    else if(result.size()!=n) cout<<"IMPOSSIBLE\n";
    else{
        for(int i=0;i<n;i++){
            cout<<result[i]<<" ";
        }
        cout<<"\n";
    }
}

int main()
{
    int t;
    cin>>t;
    
    while(t--){
        cin>>n;
        bool v[501];
        memset(v, false, sizeof(v));
        r.assign(n+1,0);
        for(int i=0;i<=501;i++) map[i].clear();
        
        for(int i=0;i<n;i++){
            int tmp;
            cin>> tmp;
            v[tmp]=true;
            for(int j=1;j<=n;j++){
                if(!v[j]){
                    map[tmp].push_back(j);
                    r[j]++;
                }
            }
        }
        
        cin>>m;
        for(int i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            vector<int>::iterator it = find(map[y].begin(), map[y].end(), x);
          
            if(it!= map[y].end()){
                map[y].erase(it);
                map[x].push_back(y);
                r[x]--;
                r[y]++;
            } else{
                it = find(map[x].begin(), map[x].end(), y);
                map[x].erase(it);
                map[y].push_back(x);
                r[x]++;
                r[y]--;
            }
           
        }
        solve();
        
    }
    return 0;
}