1707_이분그래프

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

1707번: 이분 그래프

"그래프 이론에서, 이분그래프란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강 색과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다." - wiki

 

좀 더 설명하자면, 이 문제에서 

위와 같은 그림은 이분 그래프이다. 한 정점이 빨간색이면 간선으로 연결된 정점은 다른 색을 가져야 한다. 같은 색을 가지게 되면 이분 그래프가 아니다. 

위와 같은 그래프를 보면 이 그래프가 이분 그래프가 되려면 4번 정점은 빨간색을 가져도 안되고 파란색을 가져도 안된다. 그러므로 이 그래프는 이분 그래프가 될 수 없다. 

 

위와 같은 이론을 이용하여 BFS를 사용하여 풀었다. 한 정점을 큐에 넣고 색깔을 넣어준 다음 정점과 연결된 선에는 다른 색을 넣어줬다. 만약 이미 색깔이 있는 곳에 다른 색깔로 들어가려고 하면 그것은 이분 그래프가 아닌것이다. 

 

#include<bits/stdc++.h>
 
using namespace std;
 
int color[20001];
vector<int> graph[20001];
 
int bfs(int n, int flag){
    queue<int> q;
    q.push(n);
    while(q.size()){
        int t = q.size();
        while(t--){
            int tmp = q.front();
            if(color[tmp] == 0)
            {
                color[tmp] = flag;
                for(int i = 0; i < graph[tmp].size();i++)
                    q.push(graph[tmp][i]);
            }
            else if(color[tmp] != flag) return 0;
            q.pop();
        }
        flag *= -1;
    }
    return 1;
}
 
 

#include<bits/stdc++.h>
 
using namespace std;
 
int color[20001];
vector<int> graph[20001];
 
int bfs(int n, int flag){
    queue<int> q;
    q.push(n);
    while(q.size()){
        int t = q.size();
        while(t--){
            int tmp = q.front();
            if(color[tmp] == 0)
            {
                color[tmp] = flag;
                for(int i = 0; i < graph[tmp].size();i++)
                    q.push(graph[tmp][i]);
            }
            else if(color[tmp] != flag) return 0;
            q.pop();
        }
        flag *= -1;
    }
    return 1;
}
int main(void){
    int k;
 
    cin >> k;
    while(k--){
        int v, e, v1, v2;
        set<int> se;
        set<int>::iterator it;        
        memset(graph, 0, sizeof(color));
        memset(graph, 0, sizeof(graph));
        cin >> v >> e;
        for(int i = 0; i < e ;i++){
            cin >> v1 >> v2;
            graph[v1].push_back(v2); graph[v2].push_back(v1);
            se.insert(v1); se.insert(v2);
        }
        flag = 0;
        for(it = se.begin(); it != se.end();it++){
            if(color[*it]) continue;
            if(!bfs(*it, 1)) break;
        }
        if(it == se.end())
            cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
}