[백준] 28146 - Broken Minimum Spanning Tree (c++)

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

 

문제 요약

N개의 정점과 M개의 간선으로 구성된 무향 가중치 그래프와 스패닝 트리 S가 주어진다. 

S를 MST로 만들기 위해 최소한의 간선 스왑을 수행하는 과정을 출력하라.

간선 스왑이란, 스패닝 트리에서 간선 하나를 제거하고 스패닝 트리 상태를 유지하면서 그래프의 다른 간선을 추가하는 동작이다.

 

풀이 (M^2)

• MST
• 트리 셋
• DFS

크루스칼을 한 번 돌리는데 정렬에서 가중치가 같을 때 S의 간선이 우선이 되게 한다. 이렇게 얻은 MST에서 S에 포함되지 않는 간선을 하나씩 추가한다. 간선을 추가하면 사이클이 하나 생기는데 DFS로 가중치가 최대인 간선을 찾아 삭제하면 된다. 간선을 추가하고 삭제하는 것은 트리 셋으로 할 수 있다.

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

struct Djs {
    vector<int> p;
    Djs(int size) {
        p.resize(size,0);
    }
    int find(int a) {
        if (!p[a])
            return a;
        return p[a] = find(p[a]);
    }
    void Union(int a, int b) {
        p[find(a)] = find(b);
    };
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    vector<set<array<int,3>>> adj(n+1);
    vector<array<int,4>> ed;
    for(int i=1,u,v,c;i<=m;i++) {
        cin>>u>>v>>c,ed.push_back({c,i,u,v});
        if(i<n)adj[u].insert({v,c,i}),adj[v].insert({u,c,i});
    }
    
    sort(ed.begin(),ed.end());
    Djs djs = Djs(n+1);
    vector<array<int,2>> ans;
    auto dfs = [&](int u,int p,int s,auto f)-> array<int,4> {
        if(u==s) 
            return {0,0,0,0};
        for(auto [v,c,i]:adj[u]) if(v!=p) {
            auto ret =f(v,u,s,f);
            if(ret[0]!=2e9)return max(ret,{c,i,v,u});
        }
        return {(int)2e9,0,0,0};
    };
    for(auto [c,idx,u,v]:ed) {
        if(djs.find(u)!=djs.find(v)) {
            djs.Union(u,v);
            if(idx>=n) {
                auto[d,j,x,y]=dfs(u,0,v,dfs);
                ans.push_back({j,idx});
                adj[x].erase({y,d,j});
                adj[y].erase({x,d,j});
                adj[u].insert({v,c,idx});
                adj[v].insert({u,c,idx});
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto[x,y]:ans)
        cout<<x<<' '<<y<<'\n';
}