백준 1707 - 이분 그래프(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

이분 그래프가 어떤 것인지는 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog

이분의 깃허브를 참고했습니다!

 

문제 접근 방법

 

1. 백터를 이용하여 각 정점에서 갈 수 있는 다른 정점들을 저장한다.

2. DFS를 통해서 현재 정점을 통해서 갈 수 있는 다른 정점들을 다른 색으로 저장한다.(1 -> 0 or 0 -> 1)

3. 그래프를 전체 탐색하여 이분 그래프를 만족하는지를 알아본다.

 

 

문제 접근 방법 - 2번

void dfs(int x) {
    for (int i = 0; i < line[x].size(); i++) {
        if (check[line[x][i]] == 0) {
            if (check[x] == 1) check[line[x][i]] = 2;
            else check[line[x][i]] = 1;
            dfs(line[x][i]);
        }
    }
}
// main 함수에 있는 DFS 사용 코드입니다.	
    for (int i = 1; i <= V; i++) {
            if (check[i] == 0) {
                check[i] = 1;
                dfs(i);
            }
        }

이분 그래프는 2가지 색을 사용하는 것이 특징입니다.

A 정점에서 B 정점으로 갈 수 있다고 했을때, A -> 0, B -> 1로 저장합니다. B에서 C로 갈때는 C -> 0으로 저장해야됩니다.

저는 시작점을 1로 저장을 한뒤 DFS 탐색을 시작했습니다. 

 

 

문제 접근 방법 - 3번

bool graph() {
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < line[i].size(); j++) {
            int x = line[i][j];
            if (check[x] == check[i]) return false;
        }
    }
    return true;
}

DFS를 통해서 탐색한 그래프가 이분 그래프인지를 확인하는 함수입니다.

자신과 연결된 정점들이 자신과 같은 색이라면 이분 그래프가 안되니, 바로 false를 return 했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int test_case;
int V, E;
int check[20001];
vector<int> line[20001];

void dfs(int x) {
    for (int i = 0; i < line[x].size(); i++) {
        if (check[line[x][i]] == 0) {
            if (check[x] == 1) check[line[x][i]] = 2;
            else check[line[x][i]] = 1;
            dfs(line[x][i]);
        }
    }
}

bool graph() {
    for (int i = 1; i <= V; i++) {
        for (int j = 0; j < line[i].size(); j++) {
            int x = line[i][j];
            if (check[x] == check[i]) return false;
        }
    }
    return true;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for (int k = 0; k < test_case; k++) {
        cin >> V >> E;
        for (int i = 0; i < E; i++) {
            int x, y;
            cin >> x >> y;
            line[x].push_back(y);
            line[y].push_back(x);
        }
        for (int i = 1; i <= V; i++) {
            if (check[i] == 0) {
                check[i] = 1;
                dfs(i);
            }
        }
        if (graph()) cout << "YES\n";
        else cout << "NO\n";
        for (int i = 1; i <= V; i++) line[i].clear();
        memset(check, 0, sizeof(check));
    }
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!