이분 그래프
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;
}
Author And Source
이 문제에 관하여(이분 그래프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aram_father/이분-그래프저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)