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

Embedded June·2020년 8월 28일
0

알고리즘::백준

목록 보기
36/109

문제

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

문제접근

  • 주어진 그래프가 이분 그래프인지 아닌지 여부를 판별하는 문제다.
  • 이분 그래프를 판단하는 문제는 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를 위해 전역변수들 초기화하기.
	}
}

결과

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글