알고리즘 스터디

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

1707번: 이분 그래프

 

처음에 무작정 DFS로 풀려고 전에 풀었던 문제들처럼 단순하게 생각해서 왔던 길만 체크했더니 당연히 실패했다.

 

이분그래프에대해서 검색하다가 각 정점이 파란색/빨간색으로 이루어져서 각각 연결된 그림을 보게되었고 그 아이디어로 문제를 풀게 되었다.

 

방문하지않은 정점은 0, 방문한 정점은 각각 1, 2로 교차하면서 체크해준다.

 

#include <iostream>
#include <vector>

using namespace std;

int k, v, e;
int u1, u2;
vector<int> visited;
vector<vector<int>> m;

void Dfs(int x, int color) {
	visited[x] = color;
	for (auto mxi : m[x]) {
		if (visited[mxi] == 0) {
			Dfs(mxi, 3 - color);
		}
	}
}

bool IsBipartite() {
	for (int i = 1; i <= v; ++i) {
		for (auto mij : m[i]) {
			if (visited[i] == visited[mij]) return false;
		}
	}

	return true;
}

void Solve() {
	visited.assign(v + 1, 0);
	m.assign(v + 1, vector<int>(0));

	for (int i = 0; i < e; ++i) {
		cin >> u1 >> u2;
		m[u1].push_back(u2);
		m[u2].push_back(u1);
	}

	for (int i = 1; i <= v; ++i)
		if (visited[i] == 0) 
			Dfs(i, 1);

	if (IsBipartite()) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> k;

	for (int i = 0; i < k; ++i) {
		cin >> v >> e;
		Solve();
	}

	return 0;
}