백준 이분그래프 (c++)

문제

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

해결

• 이분 그래프는 하나의 집단에서는 서로 연결이 안되어있는 것이다.

• 이분 그래프를 만들려면 자신의 집단(자신과 연결된 노드와는 다른 것으로 구분이 되어있어야한다)

• 구분을 지어서 이분 그래프를 만들어야하는데 그것은 예를 들어서 A노드가 레드이면 A노드와 연관되어있는 B노드는 레드가 아닌 다른색으로 색칠 되어있어야한다. 그렇게 하면 이분그래프가 완성된다.

주의

• 여기서 처음에 bfs(1)로만 돌렸다가 로직을 for문으로 모두다 보는 것으로 변경했다, 그래프가 하나가 아니라 여러개도 나올 수 있는건가?..

소스

#include <bits/stdc++.h>

using namespace std;

#define RED 1
#define BLACK 0

/*
같은 집합에 속한 것끼리 간선이 존재하지  않도록 정점을 두 집합으로 나눌 수 있을 때 이분그래프가 될 수 있다

=> 한점(한쪽 집합)을 지웠을 때 남은 정점끼리는 연결 되지 못한다.
=> bfs를 탐색하기전에 한 노드의 색을 정해주고, 이후 한 노드에 연결된 노드는 반대의 색을 가지도록한다. 
1 3
2 3 

*/
vector<int> Graph[200011];
int t, v, e;
int visited[200011]; //색 넣자 

void bfs(int Node)
{
    queue<int> q;
    q.push(Node);
    //첫색 RED    
    visited[Node] = RED;

    while (!q.empty())
    {
        int now = q.front();
        int nowColor = visited[now];

        q.pop();

        for (int i = 0; i < Graph[now].size(); i++)
        {
            int nx = Graph[now][i];

            if (visited[nx] != -1) continue;

            if (nowColor == BLACK) {
                q.push(nx);
                visited[nx] = RED;    
            }
            else {
                q.push(nx);
                visited[nx] = BLACK;
            }
        }
    }
}

bool is_bipartite()
{

    for (int i = 1; i <= v; i++)
    {
        for (int j = 0; j < Graph[i].size(); j++)
        {
            if (visited[i] == visited[Graph[i][j]]) {
                //나랑 연결되어있는데 색이 같네? -> 이분그래프가 아니다 
                return false;
            }
        }
    }
    return true;
}
void Solution()
{
    cin >> v >> e;
    //초기의 모든 노드의 색을 -1으로 두자! 
    memset(visited, -1, sizeof(visited));
    memset(Graph, 0, sizeof(Graph));

    for (int i = 0; i < e; i++)
    {
        int _a = 0, _b = 0;
        cin >> _a >> _b;

        Graph[_a].push_back(_b);
        Graph[_b].push_back(_a);
    }

    //bfs(1);
    for (int i = 1; i <= v; i++)
    {
        if (visited[i] == -1) {
            bfs(i);
        }
    }

    if (is_bipartite())
    {
        cout << "YES" << endl;
        return;
    }

    cout << "NO" << endl;
    return;
} 
int main()
{
    cin >> t;

    while (t--)
    {
        Solution();

        //출력 디버깅용 
        /*for (int i = 1; i <= v; i++)
        {
            cout << visited[i] << endl;
        }*/
    }

    return 0;
}