백준 1707번: 이분 그래프

[문제 링크]

1707번: 이분 그래프

---

BFS를 통해 같은 집합에 속한 정점들을 방문하면서 같은 레벨에 속한 정점들을 같은 숫자로 마킹한다.

이 과정에서 같은 레벨에 속했는데 이미 다른 숫자로 마킹이 되어있는 정점이 있는 경우 그 그래프는 이분그래프가 아니게 되므로 false를 반환한다.

 

모든 정점을 방문할 때 까지 위 과정을 반복하면서 false를 반환하지 않았다면 이분그래프이므로 true를 반환하도록 구현하면 원하는 결과를 얻을 수 있다.

---

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

int V, E;
vector<int> adj[20001];
vector<int> visited;

bool bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 1 });
	visited[start] = 1;

	while (!q.empty()) {
		int here  = q.front().first;
		int color = q.front().second;
		q.pop();

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			
			if (visited[there] == 0) {
				visited[there] = -color;
				q.push({ there, -color });
			}
			else
				if (visited[there] != -color)
					return false;
		}
	}

	return true;
}

bool bfsAll() {
	visited = vector<int>(V + 1, 0);

	for (int i = 1; i <= V; i++)
		if (visited[i] == 0)
			if (!bfs(i)) return false;

	return true;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		cin >> V >> E;
		for (int i = 1; i <= V; i++)
			adj[i].clear();

		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		if (bfsAll())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 164 day