(c++)백준 1707번: 이분 그래프

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

1707번: 이분 그래프

[풀이]

bfs와 dfs로 모든 정점을 돌면서 서로 이어진 정점들을 다른 그룹에 넣는 방식으로 풀었다.

 

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

int K, V, E;
vector<int>Graph[20001];//각 정점에 연결된 간선 저장
int Group[20001];//그룹 1, 그룹 2, 0이면 아직 방문X

void init() {
	for (int i = 1; i <= V; i++) {
		Graph[i].clear();
		Group[i] = 0;
	}
}

//bfs로 풀었을 때
void bfs(int start) {
	queue<int>q;
	int g = 1;
	Group[start] = g;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		g = 3 - Group[cur];//cur정점과 이어진 정점들은 다른 그룹에 넣기
		q.pop();
		for (int i = 0; i < Graph[cur].size(); i++) {
			int k = Graph[cur][i];
			if (Group[k] == 0) {
				Group[k] = g;
				q.push(k);
			}
		}
	}
}

//dfs로 풀었을 때
void dfs(int cur, int g) {
	Group[cur] = g;
	for (int i = 0; i < Graph[cur].size(); i++) {
		int next = Graph[cur][i];
		if (Group[next] == 0)
			dfs(next, 3 - g);//cur정점과 이어진 정점을 다른 그룹에 넣기
	}
}

void solution() {
	cin >> K;
	while (K--) {
		cin >> V >> E;
		init();
		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			Graph[a].push_back(b);
			Graph[b].push_back(a);
		}
		for (int i = 1; i <= V; i++) {
			if (Group[i] == 0)
				bfs(i);//dfs(i,1)
		}
		bool Yes = true;
		for (int i = 1; i <= V; i++) {
			for (int j = 0; j < Graph[i].size(); j++) {
				int k = Graph[i][j];
				//같은 그룹 안의 두 정점이 이어져 있으면
				if (Group[i] == Group[k]) {
					Yes = false;
					break;
				}
			}
			if (Yes == false)
				break;
		}
		if (Yes)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

int main() {
	solution();
	return 0;
}