[풀이]백준 풀이(V/1707)

문제풀이

이분그래프(1707,)

• 이분그래프: 그래프의 정점(V)을 둘로 분할하여 각 집합에 속한 정접끼리는 인접하지 않도록 분할할 수 있는 경우.

• 그래프가 이분 그래프인지 아닌지 판별하는 프로그램 작성

회고

• 메모리초과,,, connect가 너무 컸던 것 같다.
• 어짜피 방법이 잘못되었다. 문제를 잘못 이해했당

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

int dist[20001];
bool connect[20001][20001];
bool check[20001];
int k, v, e;
bool flag;

using namespace std;
//인접하지 않은 정점끼리 분할할 수 있는 경우를 찾아라.
//하나의 정점이라도 연결된 곳이 없으면 가능!
//bfs를 모든 노드에 대해 조사한 뒤
//하나라도 -1이 나오면 1 아니면 0 출력

void init() {
	for (int i = 0; i < v; i++) {
		dist[i] = 0;
		check[i] = false;
		for (int j = 0; j < v; j++) {
			connect[i][j] = false;
		}
	}
}

void find() {
	flag = false;
	for (int i = 0; i < v; i++) {
		if (dist[i] == v - 1) flag = true;
	}
}

void bfs(int start) {
	queue<int> q;
	q.push(start);
	check[start] = true;
	dist[start] = 0;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < v; i++) {
			if (!check[i] && connect[x][i]) {
				q.push(i);
				check[i] = true;
				dist[i] = dist[x] + 1;
			}
		}
	}
}
int main() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		int flagCnt = 0;
		cin >> v >> e;
		for (int j = 0; j < e; j++) {
			int u, v;
			cin >> u >> v;
			connect[u-1][v-1] = true;
		}
		bfs(0);
		find();
		//dist 값을 전수조사해서 한 정점으로부터 갈 수 없는 점이 있다면 이분그래프이다.
		if(flag) cout << "NO" << "\n";
		else  cout << "YES" << "\n";
		init();
		//for (int k = 0; k < v; k++) {
		//	bfs(k);
		//	find();
		//	if (flag == true) flagCnt++;
		//}
		//초기화 dist, connect, check
	}
}

• 다시 풀어보자 (dfs기준, 참조);

한 노드에서 연결된 다른 (모든)노드의 색깔이 다른 경우 이분그래프

이분 그래프의 예시

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int dist[20001];
int check[20001];
int k, v, e;
vector <int> graph[20001];

void init() {
	for (int j = 0; j < 20001; j++) {
		graph[j].clear();
	}
}

bool isBipartiteGraph() {
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			int next = graph[i][j];
			if (check[i]== check[next]) return false;
		}
	}
	return true;
}

void dfs(int nodeNum, int color) {

	check[nodeNum] = color;
	for (int x = 0; x < graph[nodeNum].size(); x++) {
		int y = graph[nodeNum][x];
		if (!check[y]) dfs(y, 3 - color);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin >> k;
	for (int i = 0; i < k; i++) {

		init();
		memset(check, 0, sizeof(check));

		cin >> v >> e;
		for (int j = 0; j < e; j++) {
			int u, v;
			cin >> u >> v;
			graph[u].push_back(v);
			graph[v].push_back(u);
		}

		for (int j = 1; j <= v; j++) {
			if (!check[j]) dfs(j, 1);
		}

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