이분 그래프

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

결국 이분 그래프라 함은 모든 정점 X에 대하여 모든 인접 정점 Y들이 서로 다른 집합에 들어갈 수 있음이 보장되어야 하는 것을 의미한다.

잘 생각해보면 2색을 가지고 인접한 노드끼리는 다른 색을 가지도록 그래프를 색칠하는 것과 동일하다.

DFS를 진행하면서 색을 칠하는데, 모순(인접한 노드끼리 같은 색이되는 경우)이 발생할 때 중단해주면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

size_t K;
size_t V, E;
vector<vector<int> > G;

bool Color(const size_t here, const size_t color, vector<size_t>& colors)
{
  colors[here] = color;

  for (const auto there : G[here])
  {
    if (colors[there] == 0)
    {
      if (!Color(there, (colors[here] == 1) ? 2 : 1, colors))
      {
        return false;
      }
    }
    else if (colors[there] == colors[here])
    {
      return false;
    }
  }

  return true;
}

string Solve(void)
{
  vector<size_t> colors(V, 0);

  for (size_t it = 0; it < V; ++it)
  {
    if (colors[it] == 0 && !Color(it, 1, colors))
    {
      return "NO";
    }
  }

  return "YES";
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  cin >> K;

  while (K--)
  {
    // Read Inputs
    cin >> V >> E;
    G.assign(V, vector<int>());

    for (size_t it = 0; it < E; ++it)
    {
      size_t src, dst;
      cin >> src >> dst;

      G[src - 1].emplace_back(dst - 1);
      G[dst - 1].emplace_back(src - 1);
    }

    // Solve
    cout << Solve() << '\n';
  }

  return 0;
}