Sangwon Coding
이분 그래프 본문
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
import java.util.*;
public class Main {
static int test_case, v, e;
static ArrayList<Integer>[] list; // 정점간의 인접리스트 배열
static int color[]; // 정점의 색깔 표시
static void dfs(int now, int c) {
color[now] = c;
for (int next : list[now]) { // 간선을 넘어가면서 색깔을 바꾸는 것
if (color[next] == 0) {
dfs(next, 3 - c); // 1, 2를 번갈아가면서 색칠
}
}
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
test_case = sc.nextInt();
for (int t = 0; t < test_case; t++) {
v = sc.nextInt();
e = sc.nextInt();
list = new ArrayList[v + 1];
color = new int[v + 1];
for (int i = 1; i <= v; i++) {
list[i] = new ArrayList<Integer>();
color[i] = 0;
}
for (int i = 0; i < e; i++) {
int v1, v2;
v1 = sc.nextInt();
v2 = sc.nextInt();
list[v1].add(v2);
list[v2].add(v1);
}
for (int i = 1; i <= v; i++) { // 그래프가 2개 이상으로 이루어진 것일 수도 있으므로 모든 시작점 탐색
if (color[i] == 0) // 이미 색칠한 것이면 넘어가기
dfs(i, 1);
}
boolean check = true; // 이분 그래프인지 여부
for (int i = 1; i <= v; i++) {
for (int a : list[i]) {
if (color[i] == color[a])
check = false;
}
}
System.out.println(check ? "YES" : "NO");
}
}
}
문제출처
Comments