[BOJ 23569] Friendship Graph

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

23569번: Friendship Graphs

Tag : graph theory, knapsack dp

 

문제요약

주어진 그래프를 두개의 clique로 쪼개라. (모든 정점은 두개의 clique 중 하나에 포함돼야함)

 

풀이

주어진 그래프의 complement graph를 G'라하자. G'에서 인접하지 않은 정점들은 연결돼있다.

따라서 G'의 independent set은 clique일 수 밖에 없다.

 

-1을 출력하는 경우는 G'에서 independent set 두개로 쪼갤 수 없는 컴포넌트가 존재하는 경우이다.

independent set 두개로 쪼갤 수 없는 경우는 무엇일까.

 

위처럼 이분 그래프가 아닌 경우이다. 모든 컴포넌트에서 이분 그래프인지 판별해보고 이분 그래프라면 

최소 차이를 구하는 작업을 하면 되고 아니라면 -1을 출력하면 된다.

 

두 clique의 최소 사이즈 차이는 어떻게 구할까?

G'의 각 컴포넌트에서 짝수 깊이의 정점 개수를 \(A_i\), 홀수 깊이의 정점 개수를 \(B_i\)라 하면

\((A_i-B_i)\)들로 knapsack을 돌려본 후 그 결과에서 0에 가까운 값을 고르면 된다.

 

아래와 같은 틀린 그리디를 생각해볼 수 있는데 icpc 대회 중에도 그렇고 블로그를 작성 중인 지금까지 막히지 않았다.

+ 12월 14일 재채점이 이뤄졌습니다.

sort(all(A),greater<>());
int l=0,r=0;
for(auto&i:A){
    if(l<r)l+=i;
    else r+=i;
}

이는 A에 8 7 3 3 3 3 3이 들어있는 경우가 반례이며 데이터 추가 요청도 했다

https://www.acmicpc.net/board/view/78218

 

시간복잡도 : \(O(N^2)\)

 

전체 코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,M;
int g[1010][1010];
vector<int>v[1010];
int chk[1010],dep[1010];
int p=0,q=0;

int dfs(int x){
    chk[x]=1;
    dep[x]?++p:++q;
    int f=1;
    for(auto&i:v[x]){
        if(chk[i])f&=dep[i]!=dep[x];
        else {
            dep[i]=!dep[x];
            f&=dfs(i);
        }
    }
    return f;
}

int dp[1010][5050];
int A[1010],cnt=0;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>M;
    fill(&g[1][1],&g[N+1][0],1);
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        g[a][b]=g[b][a]=0;
    }
    for(int i=1;i<=N;i++)for(int j=i+1;j<=N;j++){
        if(g[i][j]){
            v[i].pb(j);
            v[j].pb(i);
        }
    }
    for(int i=1;i<=N;i++){
        if(chk[i])continue;
        p=0;q=0;
        if(dfs(i)==0){
            cout<<-1<<endl;
            return 0;
        }
        A[++cnt]=p-q;
    }
    int base=2000;
    dp[0][base+0]=1;
    for(int i=1;i<=cnt;i++){
        for(int j=N;j>=-N;j--){
            if(dp[i-1][base+j+A[i]])dp[i][base+j]=1;
            if(dp[i-1][base+j-A[i]])dp[i][base+j]=1;
        }
    }
    int ans=1000000000;
    for(int i=-N;i<=N;i++){
        if(dp[cnt][base+i]){
            rmin(ans,abs(i));
        }
    }
    cout<<ans<<endl;
}