[백준 1707번] 이분 그래프

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

1707번: 이분 그래프

풀이)

bfs를 통해 방문하지 않은 곳을 전부 색칠한다. 여기서 나와 연결되어 있는 정점들은 계속 반대의 색상을 넣어준다. 전부를 돌면서 다 색상을 칠한 뒤 이분그래프의 개념과 동일하게 다 맞게 칠해졌는지 확인한다.

 

참고 : ko.wikipedia.org/wiki/이분_그래프

#include <iostream>
#include <vector>
#include <queue> 
#include <string.h>
using namespace std;

int K, V, E, a, b; 
vector<int> graph[20001];
int visited[20001];

void bfs(int start)
{
    queue<int> q;
 
    visited[start] = 1;
    q.push(start);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];
            if (visited[next] == -1)
            {
                visited[next] = visited[now] ? 0 : 1;
                q.push(next);
            }
        }
    }
}
 
int isBipartiteGraph()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            int next = graph[i][j];
            if (visited[i] == visited[next])
                return (0);
        }
    }
    return (1);
}
 
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> K;
    while (K--)
    {
        for (int i = 1; i <= V; i++)
            graph[i].clear();
        memset(visited, -1, sizeof(visited));
        cin >> V >> E;
        while (E--)
        {
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        for (int i = 1; i <= V; i++)
            if (visited[i] == -1)
                bfs(i);
        if (isBipartiteGraph())
            cout << "YES\n";
        else 
            cout << "NO\n";
    }
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!