[BOJ] 18919 Allowed Swaps

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

18919번: Allowed Swaps

\(x, y\) 쌍이 들어오면 \(x\) 와 \(y\)를 이어주는 간선을 만들어준다.

그러면, 그래프가 형성되는데, 사이클이 존재유무는 문제를 푸는데 전혀 도움이 되지 않기 때문에, 트리로 만들고 생각을 한다.

 

그러면 이제 적절히 스왑을 해줄텐데, 가장자리에 있는 노드부터 처리해주면 나중에 처리하는 노드에 전혀 관여하지 않기 때문에 위상정렬 느낌으로 degree가 1인 노드부터 그 노드의 인덱스가 제자리에 찾아오는 방법을 사용하면 된다.

 

위의 이미지의 경우 인덱스가 3인 노드에 수 3이 오기 위해 스왑해야 하는 방법이다.

이를 총 \(N\)번 반복해주면, 시간 복잡도는 \(O(N^{2})\)로 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,p[1005];
int a[1005],deg[1005];
bool c[1005];
vecpi v[1005],ans;

bool dfs(int x,int fi) {
    if(a[x] == fi) return 1;
    c[x] = 1;
    for(pi i : v[x]) {
        if(c[i.x]) continue;
        if(dfs(i.x,fi)) {
            swap(a[i.x],a[x]);
            ans.pb((i.y ? mp(i.x,x) : mp(x,i.x)));
            return 1;
        }
    }
    return 0;
}

int Find(int x) {return (x^p[x] ? p[x] = Find(p[x]) : x);}
bool merge(int x,int y) {
    x = Find(x), y = Find(y);
    if(x == y) return 0;
    p[y] = x; return 1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i], p[i] = i;
    int m; cin >> m;
    while(m--) {
        int x,y; cin >> x >> y;
        if(merge(x,y)) v[x].pb({y,0}), v[y].pb({x,1}), deg[x]++, deg[y]++;
    }
    queue <int> q;
    for(int i = 1;i <= n;i++) {
        if(deg[i] == 1) q.push(i);
    }
    while(!q.empty()) {
        int x = q.front(); q.pop();
        memset(c,false,sizeof(c));
        if(!dfs(x,x)) {
            cout << -1;
            return 0;
        }
        for(pi i : v[x]) {
            if(--deg[i.x] == 1) q.push(i.x);
        }
    }
    cout << ans.size() << '\n';
    for(pi i : ans) {
        cout << i.x << ' ' << i.y << '\n';
    }
}