BOJ 1707 : 이분 그래프 [C++]

 

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

1707번: 이분 그래프

 

문제 요약

주어진 그래프가 이분 그래프인지 판별하는 문제이다.

 

이분 그래프(Bipartite Graph)?

그래프의 정점의 집합을 둘로 분할했을 때, 각 집합에 속한 정점끼리 서로 인접하지 않게 할 수 있는 그래프이다.

 

접근

이분 그래프를 모르는 상태에서 문제를 접하다보니 구현에 실수가 조금 있었다.

양방향 그래프를 입력 받고, visit배열을 통해 방문 여부를 확인하며 평범한 DFS를 구현했다.

이분 그래프를 만족시키는지 확인하기 위해 DFS함수의 두 번째 인자로 해당 정점이 속해있는 집합 번호를 넘겨주고, 그 번호를 해당 정점의 visit배열에 저장하는 식으로 구현했다.

예를 들어, 1번 정점부터 DFS를 시작한다고 하자. 1번 정점은 집합 1에 속한다. ( visit[1] = 1 )
다음 정점으로 DFS를 수행할 때는 다음 정점이 들어가야 할 집합의 번호를 넘겨준다.

이렇게 DFS를 수행하다 보면 next정점이 이미 방문한 적이 있는데, 현재 정점과 집합의 번호가 같은 경우가 있다. 이 경우에는 이분 그래프의 성질이 깨지므로 false를 리턴한다. 그렇지 않으면 이분 그래프를 만족하므로 나머지 경우에 대해선 true를 리턴한다.

반복문을 통해 1번 정점부터 N번 정점까지 DFS를 수행하면서 각 수행 결과를 모두 AND한 값이 true이면 이분 그래프이다.

 

#include <iostream>
#include <queue>
using namespace std;

int N, M, T, a, b;
vector<vector<int> > V;
vector<int> visit;

bool dfs(int n, int c) {
	visit[n] = c;
	bool temp = true;
	for (int i : V[n]) {
		if (visit[i] == c)	return false;
		if (!visit[i])	temp &= dfs(i, c == 2 ? 1 : 2);
	}
	return temp;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (cin >> T; T--;) {
		cin >> N >> M;
		V = vector<vector<int> >(N + 1);
		visit = vector<int>(N + 1, 0);
		for (; M--;) {
			cin >> a >> b;
			V[a].push_back(b);
			V[b].push_back(a);
		}
		bool ans = true;
		for (int i = 1; i <= N; i++) {
			if (!visit[i])	ans &= dfs(i, 1);
		}
		cout << (ans ? "YES" : "NO") << '\n';
	}
}