반응형
알고리즘 분류 : DFS
DFS를 이용하여 이분 그래프인지 아닌지 확인할 수 있다. 이분 그래프(Bipartite graph)란, 인접한 노드는 서로 다른 색의 노드로 구분되고, 그래프 내의 모든 노드를 두 가지 색으로만 칠할 수 있는 그래프를 말한다.
- DFS 탐색을 통해 아직 방문하지 않은 노드(0)를 방문한다. 방문할 때 어떤 색인지 표시해둔다.
- 이 코드에서는 2개의 그룹으로 나눈다고 가정하고, 1과 -1의 그룹으로 구분했다.
- 다음 노드는 현재 그룹 번호에 -1을 곱해서 1과 -1을 교차하여 그룹 짓도록 했다.
- 만약 다음 노드가 이미 방문한 노드라면, 현재 노드의 그룹 번호와 다음 노드의 번호가 같은지 확인한다.
- 번호가 같으면 인접한 노드가 같은 그룹이므로, false를 리턴한다.
- DFS 탐색이 끝날 때 까지 false를 리턴하지 않았다면, 모든 노드를 이분화하는 것에 성공했으므로 true를 리턴한다.
C++ 소스코드
#include <cstdio> #include <vector> using namespace std; vector<int> a[20001]; int check[20001]; bool dfs(int now, int group) { check[now] = group; // Groups are divided into 1 or -1. for (int i=0; i<(int)a[now].size(); i++) { int next = a[now][i]; if (check[next] == 0) { if (!dfs(next, -group)) { return false; } } else if (check[next] == check[now]) { // Adjacent nodes have same color. return false; } } return true; } int main() { int k, v, e; scanf("%d", &k); while (k--) { scanf("%d %d", &v, &e); for (int i=1; i<=v; i++) { // Initialize a[i].clear(); check[i] = 0; } int x, y; for (int i=0; i<e; i++) { scanf("%d %d", &x, &y); a[x].push_back(y); a[y].push_back(x); } bool ans = true; for (int i=1; i<=v; i++) { if (check[i] == 0) { if (!dfs(i, 1)) { ans = false; break; } } } printf("%s\n", ans ? "YES" : "NO"); } return 0; }
Python 3 소스코드
import sys sys.setrecursionlimit(100000) input = sys.stdin.readline def dfs(now, group, a, check): check[now] = group for i in a[now]: if check[i] == 0: if dfs(i, -group, a, check) is False: return False elif check[i] == check[now]: return False return True for _ in range(int(input())): v, e = map(int, input().split()) a = [[] for _ in range(v+1)] check = [0]*(v+1) for _ in range(e): x, y = map(int, input().split()) a[x].append(y) a[y].append(x) ans = True for i in range(1, v+1): if check[i] == 0: if dfs(i, 1, a, check) is False: ans = False break print("YES" if ans else "NO")
참고
반응형