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

문제 바로가기
DFS를 사용한 문제이다.

처음에 사이클을 판단하는 문제인줄알고, union find를 사용하려 했지만, 이분 그래프는 사이클과는 무관하였다.

이분그래프를 판단하는 방법은 쉽다.

1. 한 점에서 빨강 또는 파랑에서 시작하고, 그래프를 다 색칠한다
2. 그다음 노드를 잇는 선에서 빨강 빨강, 파랑 파랑으로 이어지는 선이 있는지 판별하면 된다.

방문처리와 graph 배열을 전역변수로 선언하였다.

vector<int> graph[200001];
int visited[200001];

int main() {
	int K = 0;
	cin >> K;

	for (int i = 0; i < K; i++) {
		int V = 0;
		int E = 0;
		cin >> V >> E;
		for (int j = 0; j < E; j++) {
			int a = 0;
			int b = 0;
			cin >> a >> b;

			graph[a].push_back(b);
			graph[b].push_back(a);
		}
        ...

먼저, 간선을 받으면서 graph에다가 넣어주었다.
중요한점은 무방향 그래프이므로 각각 a,b b,a 두개를 넣어야한다는 것이다.

		for (int j = 1; j <= V; j++) {
			if (visited[j] == 0) {
				dfs(j, 1);
			}
		}

그다음 dfs를 각 노드마다 돌면서 그래프를 색칠한다.
여기서 1부터 V까지 노드를 준 이유는, 각 노드가 끊겨 있을 수 도 있기 때문이다.
1-2-3 4-5 이런식으로 그래프가 되어있으면 1부터에서만 시작하면 4,5는 색칠 할 수 없다.

void dfs(int start, int color) {
	if (!visited[start]) {
		if (color == 1) {
			visited[start] = 1;
		}
		else {
			visited[start] = 2;
		}
	}

	for (int i = 0; i < graph[start].size(); i++) {
		if (!visited[graph[start][i]]) {
			if (color == 1) {
				dfs(graph[start][i], 2);
			}
			else {
				dfs(graph[start][i], 1);
			}
		}
	}
}

처음에는 무조건 1로 색칠하고 다음 노드는 2로 색칠 그다음은 1로 색칠하면서 반복했다.

		bool flag = true;
		for (int i = 1; i <= V; i++) {
			int c = visited[i];
			for (int j = 0; j < graph[i].size(); j++) {
				if (visited[graph[i][j]] == c) {
					flag = false;
					break;
				}
			}
			if (!flag) break;
		}

		if (!flag) {
			cout << "NO"<<"\n";
		}
		else {
			cout << "YES"<<"\n";
		}

		for (int i = 0; i <= V; i++) {
			graph[i].clear();
		}
		memset(visited, false, sizeof(visited));
		

마지막으로 각 노드를 돌면서 자신이 1인데 방문할수 있는 노드중에서 2가 아니라 1이 있다면 이분그래프가 아닌것이다.

그리고, 전역변수를 초기화 해준다.

전체 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
vector<int> graph[200001];
int visited[200001];

void dfs(int start, int color) {
	if (!visited[start]) {
		if (color == 1) {
			visited[start] = 1;
		}
		else {
			visited[start] = 2;
		}
	}

	for (int i = 0; i < graph[start].size(); i++) {
		if (!visited[graph[start][i]]) {
			if (color == 1) {
				dfs(graph[start][i], 2);
			}
			else {
				dfs(graph[start][i], 1);
			}
		}
	}
}

int main() {
	int K = 0;
	cin >> K;

	for (int i = 0; i < K; i++) {
		int V = 0;
		int E = 0;
		cin >> V >> E;
		for (int j = 0; j < E; j++) {
			int a = 0;
			int b = 0;
			cin >> a >> b;

			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		for (int j = 1; j <= V; j++) {
			if (visited[j] == 0) {
				dfs(j, 1);
			}
		}

		bool flag = true;
		for (int i = 1; i <= V; i++) {
			int c = visited[i];
			for (int j = 0; j < graph[i].size(); j++) {
				if (visited[graph[i][j]] == c) {
					flag = false;
					break;
				}
			}
			if (!flag) break;
		}

		if (!flag) {
			cout << "NO"<<"\n";
		}
		else {
			cout << "YES"<<"\n";
		}

		for (int i = 0; i <= V; i++) {
			graph[i].clear();
		}
		memset(visited, false, sizeof(visited));
		
	}
}