BOJ 3682 - 동치 증명

문제 링크 : https://www.acmicpc.net/problem/3682

문제 풀이

 최소 간선을 추가해서 전체를 하나의 SCC로 만드는 문제이다. 

 먼저 주어진 그래프를 생각해보자. 애초에 문제에서 하나의 SCC 로 만드는 것이 목표이기 때문에 그래프를 SCC 간의 위상정렬로 놓고 생각하지 않을 이유가 없다. 따라서 그래프에서 먼저 SCC를 구하자. SCC 내에서는 서로 동치이기 때문에 추가적인 간선을 이을 필요가 없다. 따라서 처음에 구한 하나의 SCC 는 하나의 정점으로 대체하여 생각할 수 있다. 

 그렇게 변형된 그래프를 생각해보자. 그래프에는 사이클이 존재하지 않는다. 여기서 모든 정점을 묶어서 SCC로 만들어 주어야 한다. 이를 위해서는 모든 정점의 outdegree와 indegree가 1 이상이어야 한다. 즉, outdegree가 없는 정점들에서 나가는 간선이 하나씩 추가되어야 하고, indegree가 없는 정점들로 들어가는 간선이 하나씩은 존재해야 한다. outdegree가 없는 정점에서 indegree가 없는 다른 정점으로 이어주면 되기 때문에, 필요한 간선의 개수는 max(outdegree가 없는 정점의 수, indegree가 없는 정점의 수) 가 된다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct poi{
    ll val,xx,yy;
};
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[101101];
ll ind[101101];
ll oud[101101];
 
vector<ll> v[101101];
vector<ll> rev[100101];
vector<ll> scc[100101];
ll vis[1010101];
stack<ll> st;
vector<ll> gv[101101];
ll gind[100101];
ll goud[100101];
ll num[101101];
ll gp;
 
void dfs(ll x){
    vis[x]=1;
    for(auto k:v[x]){
        if(vis[k]) continue;
        dfs(k);
    }
    st.push(x);
}
 
void dfs2(ll x){
    vis[x]=1;
    num[x]=gp;
    for(auto k:rev[x]){
        if(vis[k]) continue;
        dfs2(k);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--){
        ll i,j,k,a=0,b=0,c,d,e,f;
        cin>>n>>m;
        for(i=1;i<=n;i++){
            v[i].clear();
            rev[i].clear();
            ind[i]=oud[i]=0;
            gind[i]=goud[i]=0;
            gp=0;
        }
        while(m--){
            cin>>a>>b;
            v[a].pb(b);
            rev[b].pb(a);
        }
 
        for(i=1;i<=n;i++)
            vis[i]=0;
        
        for(i=1;i<=n;i++){
            if(vis[i]) continue;
            vis[i]=1;
            dfs(i);
        }
 
        for(i=1;i<=n;i++)
            vis[i]=0;
 
        while(st.size()){
            ll x=st.top();
            st.pop();
            if(vis[x]) continue;
            vis[x]=1;
            gp++;
            dfs2(x);
        }
 
        for(i=1;i<=n;i++){
            for(auto j:v[i]){
                if(num[i]==num[j]) continue;
                gind[num[j]]++;
                goud[num[i]]++;
            }
        }
        ll c1=0,c2=0;
        if(gp==1){
            cout<<0<<'\n';
            continue;
        }
 
        for(i=1;i<=gp;i++){
            if(!gind[i]) c1++;
            if(!goud[i]) c2++;
        }
 
        cout<<max(c1,c2)<<'\n';
    }
 
 
}