백준 1707 이분 그래프

이분 그래프란? 정점에 색깔을 부여한다고 할 때, 절반씩 그룹으로 나눌 수 있는 그래프. 인접한 정점끼리 색깔이 같으면 안 된다

골4 문제이지만 이제까지 풀어왔던 dfs, bfs처럼 탐색으로 풀 수 있다

 

1. 탐색하면서 그래프에 색깔(1, 2)을 부여한다. visit를 체크할 때 방문/미방문이 아닌, 미방문/색1/색2 이렇게 세 가지로 주면 된다

위에 그림에서는 문제의 예시로 있는 두 케이스를 그림으로 그린 것이다

O가 색1, X가 색2라고 했을 때, 탐색이 끝나면 각 정점에 대해 O또는 X가 전부 부여된다(미방문이 없을 때까지 탐색)

 

2. 각 정점에 연결된 정점들을 확인하며 색1의 연속, 색2의 연속인 경우가 있는지 체크한다

각 정점에 연결된 정점들을 이중for문으로 확인하며 OO또는 XX가 나오면 이분 그래프가 아님(1), 그렇지 않다면 이분 그래프임(2) 이다

 

<전체 코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
vector<int>a[20001];
//int a[20001][20001];
int visit[20001];
int n, m;

//1빨강 2검정
void dfs(int now) {
    if (!visit[now]) visit[now] = 1;
    for (int i = 0; i < a[now].size(); i++) {
        int next = a[now][i];
        if (!visit[next]) {
            if (visit[now] == 1) visit[next] = 2;
            else if (visit[now] == 2) visit[next] = 1;
            dfs(next);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        memset(visit, 0, sizeof(visit));
        cin >> n >> m;
        for (int i = 0; i <= n; i++) {
            a[i].clear();
        }

        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            a[x].push_back(y);
            a[y].push_back(x);
            //a[x][y] = a[y][x] = 1;
        }

        for (int i = 1; i <= n; i++) {
            if (!visit[i]) {
                dfs(i);
            }
        }

        bool flag = false;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < a[i].size(); j++) {
                int next = a[i][j];
                if (visit[i] == visit[next]) {                   
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (!flag) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
}

github.com/proqk/Algorithm/blob/master/dfs/1707%20%EC%9D%B4%EB%B6%84%20%EA%B7%B8%EB%9E%98%ED%94%84.cpp