[백준 1707번 이분 그래프(DFS)/ C++]

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

처음에는 이분그래프가뭐지!!!! 무슨 말이 저렇게 어렵지!!!하고 있었는데 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;
}