[BOJ 1707] 이분 그래프

이 문제를 풀기전에 이분그래프가 무엇인지 먼저 설명을 하도록 하겠다.

이분 그래프란 위 그림처럼 A,B처럼 반반으로 나눌수 있는 그래프를 말한다. 즉, 모든 간선의 끝이 한쪽은 A 한쪽은 B에 속하는 그래프를 말한다.

이분 그래프를 단순히 구현하는 문제가 바로 https://www.acmicpc.net/problem/1707 이다.

해당 문제의 경우 bfs혹은 dfs를 통하여 방문하는 지점의 점수를 각각 1,2로 다르게 준 후 마지막에 비교를 하면 된다. 그리하여 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
int T,v,e,a,b;
 
int visited[22222];
bool ans;
 
vector<vector<int>>vt ;
void dfs(int node, int c){
    visited[node] = c;
    if(vt[node].size() == 0){
        ans = false;
    }
    
    for(int i=0;i<vt[node].size();i++){
        int next = vt[node][i];
        if(visited[next] == 0){
            dfs(next,3-c);
        }
    }
}
int main(){
    scanf("%d", &T);
    while(T--){
        ans = true;
        scanf("%d%d" , &v, &e);
        vt.resize(v+1);
        for (int i=1; i<=v; i++) {
            vt[i].clear();
            visited[i] = 0;
        }
        
        for(int i=1;i<=e;i++){
            scanf("%d%d" , &a, &b);
            vt[a].push_back(b);
            vt[b].push_back(a);
        }
        
        for(int i=1;i<=v;i++){
            if(visited[i] == 0){
                dfs(i,1);
            }
        }
        
        for(int i=1;i<=v;i++){
            for(int j=0;j<vt[i].size();j++){
                if(visited[i] == visited[vt[i][j]]){
                    ans = false;
                }
            }
        }
        
        if(ans == true){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
        vt.clear();
    }
    
    return 0;
}

해당 코드를 작성하였다. 하지만 결과는 fail..... 

이 부분에서 이분 그래프에 대한 또 다른 정의?를 알 수 있다.이분 그래프는 예를들어 {1/3} , {2} 의 경우에도 이분 그래프라고 칭한다. 

즉 16~18줄을 작성할 필요가 없는것이다. .... 따라서 그 부분을 제외하여 코딩을 하면 된다 .. ㅠㅠ  

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
int T,v,e,a,b;
 
int visited[22222];
bool ans;
 
vector<vector<int>>vt ;
void dfs(int node, int c){
    visited[node] = c;
    for(int i=0;i<vt[node].size();i++){
        int next = vt[node][i];
        if(visited[next] == 0){
            dfs(next,3-c);
        }
    }
}
int main(){
    scanf("%d", &T);
    while(T--){
        ans = true;
        scanf("%d%d" , &v, &e);
        vt.resize(v+1);
        for (int i=1; i<=v; i++) {
            vt[i].clear();
            visited[i] = 0;
        }
        
        for(int i=1;i<=e;i++){
            scanf("%d%d" , &a, &b);
            vt[a].push_back(b);
            vt[b].push_back(a);
        }
        
        for(int i=1;i<=v;i++){
            if(visited[i] == 0){
                dfs(i,1);
            }
        }
        
        for(int i=1;i<=v;i++){
            for(int j=0;j<vt[i].size();j++){
                if(visited[i] == visited[vt[i][j]]){
                    ans = false;
                }
            }
        }
        
        if(ans == true){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
        vt.clear();
    }
    
    return 0;
}