[Baekjoon - 10037] Decorating the Pastures

난이도: Gold II

 

태그

• Bipartite Graph

 

풀이

1. 주어진 조건을 만족하는 그래프는 어떤 모양일까?

F를 하나의 색으로, J를 다른 하나의 색으로 보면

영락없는 이분 그래프가 됩니다.

 

즉, 이분 그래프의 조건을 만족하지 않는다면 답은 자연스럽게 -1이 되겠죠.

 

2. 그럼, 문제의 답은?

이분 그래프의 각 컴포넌트를 두 색으로 나누는 방법은 유일합니다.

// 엄밀히는, 색1과 색2를 swap하는 경우를 제외하고요.

 

그러므로, 그렇게 나눈 뒤 둘 중 더 많은 쪽을 J로 정해주면 됩니다.

 

3. 코드

vector<int> adj[50020];
 
int chk[50020]; int cnt[3];
bool dfs(int now, int clr){
    chk[now] = clr; cnt[clr] += 1;
    bool res = 1;
    for (int nxt : adj[now]){
        if (chk[nxt]){ res &= (clr != chk[nxt]); }
        else{ res &= dfs(nxt, clr^3); }
    }
    return res;
}
 
void Main(){
    int n, m; cin >> n >> m;
    while (m--){
        int v, w; cin >> v >> w;
        adj[v].push_back(w); adj[w].push_back(v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (chk[i]){ continue; }
        cnt[1] = cnt[2] = 0;
        if (!dfs(i, 1)){ cout << -1; return; }
        ans += max(cnt[1], cnt[2]);
    }
    cout << ans;
}