백준[1707] - 이분 그래프

문제

백준 1707 문제 보기

접근 방법

처음 이차 배열을 다 잡아 놓고 시작했다. 그럼 128MB 밖에 안되는 문제 요건을 충족할 수 없어 vector을 활용해 추가될때마다 공간를 만드는 형식으로 변환했다. dfs를 돌며 blue, red로 번갈아가며 색을 배정한다.
dfs를 다 돌면 노드 별로 연결된 노드를 확인하며 색이 같은지만 체크하면 된다.

코드

#include <iostream>
#include <cstring>
#include <vector>

#define RED 1
#define BLUE 2

using namespace std;

int testCase, node, edge;
vector map[20001];
int visited[20001];

int dfs(int Enode, int color) {

    visited[Enode] = color;
    for(int i = 0; i < map[Enode].size(); i ++) {
        int next = map[Enode][i];
        if(!visited[next]) {
            dfs(next, 3 - color);
        }
    }

    return 0;
}

int main() {

    cin >> testCase;

//    cout << sizeof(map) << endl;
    while(testCase --) {
        memset(map, 0, sizeof(map));
        memset(visited, 0, sizeof(visited));
        cin >> node >> edge;

        for(int i = 0; i < edge; i ++) {
            int x, y;
            cin >> x >> y;

//            map[x][y] = map[y][x] = 1;
            map[x].push_back(y);
            map[y].push_back(x);
        }

        for(int i = 1; i <= node; i ++) {
            if(!visited[i])
                dfs(i, RED);
        }

        bool ok = true;
        for (int i = 1; i <= node; i++) {
            for (int k = 0; k < map[i].size(); k++) {
                int j = map[i][k];
                if (visited[i] == visited[j]) {
                    ok = false;
                }
            }
        }

        printf("%s\n", ok ? "YES" : "NO");
    }

    return 0;
}