백준 17398 통신망 분할

http://www.acmicpc.net/problem/17398 

17398번: 통신망 분할

유니온 파인드를 사용하는 문제였습니다.

 

문제를 푸는 아이디어가 재밌는 문제인데요. 처음에는 단절점, 단절선 문제같아 보였는데 시간복잡도를 보고 다른 아이디어로 푸는걸 깨달았습니다. 문제는 간선을 순서대로 빼고 나눠지는 두 연결요소의 정점 수를 곱하는거지만 거꾸로 생각해보면 문제에서 주어진 순서 반대로 간선을 추가하고 연결되는 두 연결요소의 정점 수를 곱한다고 생각해볼 수 도 있습니다. 간선을 추가할때 연결요소를 체크하면서  연결요소의 정점개수를 관리 할 수 있는 유니온파인드를 사용해 문제를 풀면 됩니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
bool temp[100001];
int parent[100001];
int urank[100001];
long long solve;
vector<pair<int,int>> E;
int N,M,Q;
int ufind(int a){
    if(a==parent[a]) return parent[a];
    return parent[a]=ufind(parent[a]);
}
void uunion(int a,int b,bool issolve){
    int k=ufind(a);
    int k2=ufind(b);
    if(k==k2) return;
    if(urank[k]>=urank[k2]){
        parent[k2]=k;
        if(issolve) solve+=(long long)urank[k]*(long long)urank[k2];
        urank[k]+=urank[k2];
    }
    else{
        parent[k]=k2;
        if(issolve) solve+=(long long)urank[k]*(long long)urank[k2];
        urank[k2]+=urank[k];
    }
}
int main(){
    fast_io();
    stack<int> stk;
    cin>>N>>M>>Q;
    for(int x=1;x<=N;x++) parent[x]=x,urank[x]=1;
    for(int x=0;x<M;x++){
        int a,b;
        cin>>a>>b;
        E.push_back({a,b});
    }
    for(int x=0;x<Q;x++){
        int input;
        cin>>input;
        stk.push(input-1);
        temp[input-1]=true;
    }
    for(int x=M-1;x>=0;x--){
        if(!temp[x]){
            uunion(E[x].first,E[x].second,false);
        }
    }
    while(!stk.empty()){
        int src=E[stk.top()].first;
        int dst=E[stk.top()].second;
        stk.pop();
        uunion(src,dst,true);
    }
    cout<<solve;
}