반응형
처음에는 이분그래프가뭐지!!!! 무슨 말이 저렇게 어렵지!!!하고 있었는데 Prof.google을 통해 알게 되었다..
정말 어렵게 설명돼 있지만 결국 서로 연결돼 있는 노드끼리 다른 그룹에 속하는 그래프를 의미한다! 더 쉽게 시각적으로 이해한다면
다음과 같다! ㅎㅎ 다음 그림을 보면 서로 연결된 노드는 다른 색을 가지고 있다 ㅎㅎ!
그럼 dfs를 통해서 한 노드에 들어갈 때마다 색깔을 이전에 노드와 다르게 저장해주면 되겠지유?!
그러고 마지막에 나와 인접한 아이가 같은 색깔을 가지고 있는지 확인하는 작업을 진행하면 끝!
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> connection[20001];
int colored[20001];
void dfs(int v, int color)
{
colored[v] = color;
for (int i = 0; i < connection[v].size(); i++) {
int to = connection[v][i];
if (!colored[to]) {
dfs(to, 3 - color);
}
}
}
bool check_color(int v_len)
{
for (int i = 1; i <= v_len; i++) {
for (int j = 0; j < connection[i].size(); j++) {
int nxt = connection[i][j];
if (colored[i] == colored[nxt])
return false;
}
}
return true;
}
int main()
{
int t, v, e;
cin >> t;
while (t--) {
cin >> v >> e;
for (int i = 0; i <= v; i++) {
connection[i].clear();
colored[i] = 0;
}
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
connection[a].push_back(b);
connection[b].push_back(a);
}
for (int i = 1; i <= v; i++) {
if (!colored[i])
dfs(i, 1);
}
if (check_color(v))
cout
<< "YES\n";
else
cout << "NO\n";
}
return 0;
}
반응형
'Algorithm 💫 > Problem Solving' 카테고리의 다른 글
[백준 4963번 섬의 개수(DFS)/ C++] (0) | 2021.01.26 |
---|---|
[백준 10451번 순열 사이클(DFS)/ C++] (0) | 2021.01.22 |
[백준 11724번 연결 요소의 개수(BFS, DFS)/ C++] (0) | 2021.01.22 |
[백준 2745번 진법 변환 / C++] (0) | 2021.01.21 |
[백준 11053번 가장 긴 증가하는 부분 수열 / C++] (0) | 2021.01.08 |
댓글