BOJ 17834 - 사자와 토끼

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

문제 풀이

문제를 보자마자 홀짝성을 생각할 수 있다. 다시 말하자면 주어진 그래프를 2가지 색으로 칠할수 있는지를 물어보는 문제이다. 만약 주어진 그래프를 2가지 색으로 칠할 수 있다면, 두 동물의 시작 색깔이 다르면 영원히 잡을 수 없게 되기 때문이다. 

주어진 그래프를 두 가지 색으로 칠할 수 있는지를 확인해 보자. 이는 dfs 한 번으로 쉽게 확인할 수 있다. dfs를 기본적으로 돌면서 두 가지 색을 번갈아가면서 칠해준다.  dfs를 돌 다 보면 이미 방문한 정점을 거를때가 있는데, 거르기 전에 현재 정점과 다른 색으로 칠해져 있는지를 확인해주면 된다. 만약 같은 색이라면 두 가지 색으로 칠할 수 없는 그래프이다. 하지만, 그러한 상황이 나오지 않는다면 두 가지 색으로 칠할 수 있는 그래프이다.

그래프를 빨간색과 파란색으로 칠했다고 하자. 두 동물이 서로 다른 색에서 출발하면 둘은 계속 다른색의 칸에 있게 되고, 따라서 잡을 수 없다. 따라서 게임이 끝나지 않는 경우는 두 동물이 서로 다른 색에서 출발하는 경우이며 이때의 경우의 수는 빨간색의 수*파란색의 수*2가 된다.

코드

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[1010101];
vector<ll> v[1010101];
ll vis[1010101];
 
ll cnt1,cnt2,mang;
 
void dfs(ll x){
    for(auto k:v[x]){
        if(vis[k]==0){
            vis[k]=3-vis[x];
            if(vis[k]==1) cnt1++;
            else cnt2++;
            dfs(k);
        }
        else if(vis[k]==vis[x]){
            mang=1;
            return;
        }
    }
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    while(m--){
        ll a,b;
        scanf("%lld %lld",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    for(i=1;i<=n;i++){
        if(vis[i]) continue;
        cnt1++;
        vis[i]=1;
        dfs(i);
    }
 
    if(mang) printf("0");
    else printf("%lld",2*cnt1*cnt2);
}