알고리즘 :: 백준 :: DFS :: 1707:: 이분 그래프

문제

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

문제접근

• 주어진 그래프가 이분 그래프인지 아닌지 여부를 판별하는 문제다.
• 이분 그래프를 판단하는 문제는 DFS 문제다.
• 임의의 시작점을 BLUE표시한 뒤 이어지는 다음 정점은 RED로 표시한다. 이런식으로 번갈아가면서 진행할 때, 이미 방문한 정점에 도달할 수 있다.
• 만일, 이미 방문한 정점이 자신과 같은 색이라면 이분 그래프가 아니다.

코드

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

static int K, N, M;
static bool ansflag;
static vector<int> graph[20001];		// 인접 리스트
static vector<int> group(20001, -1);	// n번 정점이 속한 그룹
static vector<bool> isVisited(20001);	// n번 정점 방문 여부

void dfs(int here, int g){
	if (ansflag) return;
	isVisited[here] = true;
	group[here] = g;
	for (const int& there : graph[here]) {
		if (!isVisited[there]) dfs(there, (g + 1) % 2);
		if (group[there] == group[here]) ansflag = true;
		// 중요! 현재 정점과 연결된 다음 정점이 같은 그룹에 있으면 이분그래프가 아님!
	}
}

void solve() {
	for (int startVertex = 1; startVertex <= N; ++startVertex) {
		if (!isVisited[startVertex]) dfs(startVertex, 0);
		if (ansflag) break;
	}
}

void clear() {
	for (int i = 1; i <= N; ++i) graph[i].clear();
	isVisited.assign(N + 1, false);
	group.assign(N + 1, -1);
	ansflag = false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> K;
	while(K--){
		cin >> N >> M;
		for (int i = 1; i <= M; ++i) {
			int start = 0, end = 0;
			cin >> start >> end;
			graph[start].push_back(end);
			graph[end].push_back(start);
		}
		solve();	// DFS를 이용한 이분그래프 판별.
		if (!ansflag) cout << "YES" << '\n';
		else cout << "NO" << '\n';
		clear();	// 다음 loop를 위해 전역변수들 초기화하기.
	}
}

결과