이분 그래프 - 백준 1707

Problem

난이도: 골드 4

분류: 이분 그래프, 그래프, 그래프 탐색

 

Solution

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

int main()
{
    int TestCase;
    cin >> TestCase;
    for (int i = 0; i < TestCase; i++) {
        int V, E;
        cin >> V >> E;
        vector<vector<int>> AdjList(V+1);
        for (int k = 0; k < E; k++) {
            int a, b;
            cin >> a >> b;
            AdjList[a].push_back(b);
            AdjList[b].push_back(a);
        }
        set<int> VisitedNode;
        queue<int> q;
        vector<bool> ParentNode(V + 1);
        for (int m = 0; m <= V; m++) {
            ParentNode[m] = false;
        }
        for (int u = 1; u <= V; u++) {
            if (VisitedNode.find(u) != VisitedNode.end()) continue;
            q.push(u);
            VisitedNode.insert(u);
            while (!q.empty()) {
                int CurrentNode = q.front();
                q.pop();
                for (int Nodes : AdjList[CurrentNode]) {
                    if (VisitedNode.find(Nodes) == VisitedNode.end()) {
                        VisitedNode.insert(Nodes);
                        ParentNode[Nodes] = !ParentNode[CurrentNode];
                        q.push(Nodes);
                    }
                }
            }
        }
        bool b = true;

        for (int i = 1; i <= V; i++) {
            for (int Nodes : AdjList[i]) {
                if (ParentNode[Nodes] == ParentNode[i]) {
                    b = false;
                    break;
                }
            }
        }
        if (b) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }

    }
}