백준(BOJ) 1707번 이분 그래프

문제 : https://www.acmicpc.net/problem/1707

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

나의 풀이:

이분 그래프가 되려면 DFS를 했을 시 현재 노드가 0 이라면 인접한 노드들은 1이여야 한다. 따라서 biGraph 배열을 추가로 하나 만들어서

한 노드의 인접한 노드들은 1 - (현재노드의 Bi값) 로 정의해줌으로써 현재 노드의 biGraph 값이  0 이라면 인접한 노드들은1을 1이라면 0을 반환하도록 해

주자

기존 DFS와 동일한 알고리즘에 biGraph 배열만 추가가 되고 답을 비교시에는 biGraph를 이용한다.

코드 ( C ++ )

#include <iostream>

#include <vector>

#include <cstring>

using namespace std;

const int MAX = 20000 + 1;

vector<vector<int>> adj;

vector<bool> visited;

// 이분 그래프를 판단하는 배열 Bigraph

int Bigraph[MAX];

int V, E;

void DFS(int here, int binumber)

{

visited[here] = true;

// 현재 정점에 Bigraph값은 0아니면 1

Bigraph[here] = binumber;

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i];

if (!visited[there])

// 인접한 정점에 Bigraph 값은 0이면 1 , 1이면 0

DFS(there, 1 - binumber);

}

}

bool check()

{

for (int i = 1; i <= V; ++i)

{

int here = i;

for (int j = 0; j < adj[i].size(); ++j) {

int there = adj[i][j];

// 현재 정점과 인접한 정점이 같은 Bigraph를 가지면 false후 종료한다.

if (Bigraph[here] == Bigraph[there])

return false;

}

}

return true;

}

int main()

{

int C;

cin >> C;

while (C--) {

cin >> V >> E;

// 초기화

adj = vector<vector<int>>(MAX, vector<int>());

visited = vector<bool>(MAX, false);

memset(Bigraph, 0, sizeof(Bigraph));

for (int i = 0; i < E; ++i) {

int n1, n2;

cin >> n1 >> n2;

adj[n1].push_back(n2);

adj[n2].push_back(n1);

}

for (int i = 1; i <= V; ++i)

if(!visited[i])

DFS(i, 1);

if (check())

cout << "YES" << "\n";

else

cout << "NO" << "\n";

}

return 0;

}