[ BOJ 백준 3682번 - 동치 증명 ] 해설 및 코드

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

 

목적

명제의 수 n과 증명된 함축 m개가 주어질 때, n개의 명제가 동치가 되기 위해 증명해야할 최소 함축의 개수를 구하자.

 

접근법

1. x개의 SCC를 1개로 만들기 위해 필요한 간선의 개수를 구하면 된다.

 

2. 그래프 내의 모든 정점이 사이클을 형성해야 하므로, 정점의 in-degree가 0인 정점의 개수와 out-degree가 0인 정점의 개수 중 최대값이 필요한 간선의 개수이다. 다시 말해 사이클을 형성하기 위해선, in-degree와 out-degree가 0인 정점이 하나도 없어야 한다.

 

3. 위와 같이 사이클을 형성하기 위한 조건을 알면 아주 쉬운 문제였다...

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
typedef vector<int> vi;
 
const int MAXN=2e4+1;
 
vi edge[MAXN],redge[MAXN];
int n,idx,order[MAXN],scc[MAXN],in[MAXN],out[MAXN];
bool vis[MAXN];
 
void sort(int u){
    vis[u]=true;
    for(int &v:edge[u])if(!vis[v])sort(v);
    order[idx--]=u;
}
 
void findSCC(int u){
    vis[u]=true;
    for(int &v:redge[u])if(!vis[v])findSCC(v);
    scc[u]=idx;
}
 
void countDegree(int size){
    f(i,1,n)for(int &v:edge[i])if(scc[i]!=scc[v]){
        ++out[scc[i]];
        ++in[scc[v]];
    }
}
 
int sol(){
    idx=n;
    f(i,1,n)if(!vis[i])sort(i);
    
    memset(vis, false, n+1);
    f(i,1,n)if(!vis[order[i]]){
        ++idx;
        findSCC(order[i]);
    }
    
    if(idx==1)return 0;
    
    countDegree(idx+1);
    int zeroIn=0, zeroOut=0;
    f(i,1,idx){
        if(!in[i])++zeroIn;
        if(!out[i])++zeroOut;
    }
    return max(zeroIn,zeroOut);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc;cin>>tc;
    while(tc--){
        int m;cin>>n>>m;
        f(i,1,n){
            edge[i].clear();
            redge[i].clear();
            in[i]=out[i]=vis[i]=0;
        }
        
        while(m--){
            int a,b;cin>>a>>b;
            edge[a].push_back(b);
            redge[b].push_back(a);
        }
        cout<<sol()<<'\n';
    }
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.