백준 1707. 이분 그래프 (그래프)

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

1707번: 이분 그래프

못풀어서 https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x18/solutions/1707.cpp 풀이법을 가져왔다.

 

1. 특징 

그래프

 

2. 구현 방법

이분그래프란?

- 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프

 

 

3. 코드 

#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;

int t;
int v, e;
int u, w;
vector<int> adj[20002];
int gr[20002];
bool solve()
{
    fill(gr+1, gr+v+1, -1);
    for(int i = 1; i <= v; i++)
    {
        if(gr[i] != -1) continue;
        queue<int> _queue;
        _queue.push(i);
        gr[i] = 0;

        while(!_queue.empty())
        {
            int cur = _queue.front();
            _queue.pop();

            for(auto m:adj[cur])
            {
                if(gr[m] != -1)
                {
                    if(gr[m] == gr[cur]) return false;
                    else continue;
                }
                gr[m] = (gr[cur] + 1)%2;
                _queue.push(m);

            }
        }

    }
    return true;
}

int main()
{           
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--)
    {
        cin >> v >> e;
        for(int i =1; i<=v;i++)
            adj[i].clear();
        for(int i = 0; i < e; i++)
        {
            cin >> u >> w;
            adj[u].push_back(w);
            adj[w].push_back(u);

        }

        
        if(solve()) cout << "YES\n";
        else cout << "NO\n";

    }

}