[Codeforces 1093D] Beautiful graph

[Codeforces 1093D] Beautiful graph

그래프 문제를 풀 때는 항상 Disjoint된 상태를 고려해야한다는 교훈을 일깨워준 문제. 

그래프의 vertex에 1,2,3중에 하나의 숫자를 부여해야 하는데, edge로 연결된 두 vertex끼리는 두 수의 합이 반드시 홀수가 되게 만들어야 한다. 이 조건을 만족하게 숫자를 부여하는 방법의 경우의 수를 구하는 문제이다.

내가 우선 생각한 것은 두 수를 더해서 홀수가 되도록 만드는 방법이었다. 두 수를 더해서 홀수가 되게 하려면 (짝수+홀수) 의 방법밖에 존재하지 않는다. 이 문제에서 사용할 수 있는 짝수는 2밖에 없고, 홀수는 1,3밖에 없다. 그래서 나는 그래프를 구성한 뒤 dfs를 돌면서 각 노드마다 번갈아가면서 홀->짝->홀->짝... 이렇게 부여해주었다. 그런데 문제의 예시데이터 2번처럼 중간에 홀짝이 꼬일 수도 있다. 그 경우는 밑에 소스코드상에서 21~23번 째 줄로 처리하였다. 이런 경우에는 0을 출력하면 된다. 만약 꼬이지 않고 그래프의 모든 노드가 유효하다면, 나는 그 다음에 내가 부여한 홀수의 짝수의 개수를 카운트했다. 그래서 홀수의 개수만큼 2의 거듭제곱을 취해서 답에 더하고(짝수는 어차피 '2' 하나만 존재하므로 경우의 수에 영향을 미치지 않는다), 짝수와 홀수를 서로 바꾼 경우도 있을 수 있으므로 다시 짝수의 개수만큼 2의 거듭제곱을 더했다. 이에 대한 구현이 67번 째 줄에 나와있다. 처음에 이렇게 해서 제출했더니 Wrong Answer를 받았다. 무엇이 문제인가를 봤더니 바로 그래프끼리 disjoint된 상태를 고려하지 않은 것이었다. 예를 들어 V=2,E=0인 데이터가 있다고 생각해보자. 이 상태는 서로 독립된 1번 노드와 2번 노드가 존재하는 상황이다. 각 노드에서 가능한 케이스는 3가지 이므로 3*3=9가지가 답이 되어야 한다. 그런데 내 코드는 모든 노드가 서로 연결되어있다고 가정해서 even=2, odd=0이라고 카운트한 것이다. 이러면 답이 5가 나오기 때문에 틀린 것이다. 이를 해결하기 위해선 disjoint관계에 있는 그래프끼리는 서로 경우의 수를 곱해주어야 한다. 그래프 문제는 항상 disjoint 상태를 고려하도록 하자.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define SIZE 300009
#define MOD 998244353
int V,E;
vector<int> edge[SIZE];
int mark[SIZE]={0};
int is_possible=1,even=0,odd=0;
void dfs(int node,int flag){ //flag=1 -> odd, 2 -> even
    mark[node]=flag;
    if(flag==1) odd++;
    else even++;
 
    for(int next:edge[node]){
        if(mark[next]==0){
            dfs(next,flag^3); //for 1->2->1->2...
        }
        else if(mark[next]!=(flag^3)){
            is_possible=-1;
            return;
        }
    }
    return;
}
 
long long my_pow(int a,int b){
    long long result=1;
 
    for(int i=1 ; i<=b ; i++){
        result=(result*a)%MOD;
    }
    return result;
}
void clear(){
    for(int i=1 ; i<=V ; i++){
        edge[i].clear();
        mark[i]=0;
    }
 
    is_possible=1;
    return;
}
int main(){
    int t;    scanf("%d",&t);
 
    while(t--){
        scanf("%d %d",&V,&E);
        for(int i=0 ; i<E ; i++){
            int u,v;    scanf("%d %d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
 
        long long ans=1;
        for(int i=1 ; i<=V ; i++){
            if(mark[i]==0){
                even=0,odd=0;
                dfs(i,1);
 
                if(is_possible==-1) {
                    break;
                }                
 
                ans*=(my_pow(2,odd)+my_pow(2,even));
                ans%=MOD;
            }
        }
        if(is_possible==-1) ans=0;
        printf("%lld\n",ans);
 
        clear();
 
    }
    return 0;
}