Algorithm_Practice/1707.java at master · ktyu/Algorithm_Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
importjava.util.*;

publicclassMain {

publicstaticvoidmain(String[] args) {

Scannersc = newScanner(System.in);

inttcCnt = sc.nextInt();

for (inttc = 0; tc < tcCnt; tc++) {

intn = sc.nextInt();
intm = sc.nextInt();

List<List<Integer>> nodes = newArrayList<>(n+1);
for (inti = 0; i < n + 1; i++) {
nodes.add(newArrayList<>());
 }

for (inti = 0; i < m; i++) {
inta = sc.nextInt();
intb = sc.nextInt();
nodes.get(a).add(b);
nodes.get(b).add(a);
 }

int[] check = newint[nodes.size()];

booleanisBip = true;
for(inti=1; isBip && i<nodes.size(); i++) {
if(check[i] == 0)
isBip = bfs(nodes, i, check);
 }

System.out.println(isBip ? "YES" : "NO");
 }
 }

publicstaticbooleanbfs(Listnodes, intstart, int[] check) {

Queue<Integer> q = newLinkedList<>(); // 방문해야할 노드들

q.offer(start); // 시작점 추가
check[start] = 1; // 시작점은 A그룹

while(!(q.isEmpty())) {
intnow = q.poll();

// 현재 노드에서 갈 수 있는 모든 정점에 대해 수행
for(Objectobj : (List)nodes.get(now)) {
intnum = (int)obj;

// 아직 방문 안한곳이라면
if(check[num] == 0) {
check[num] = check[now]==1 ? 2 : 1; // 색깔부여
q.offer(num); // 큐에 추가
 }

// 이미 갔다온곳이면
else {
if((check[now] != check[num])) // 색깔 다르면 넘어가기
continue;
returnfalse; // 색깔 틀리면 false 리턴
 }
 }
 }

returntrue; // 다 잘 순회했으면 true 리턴
 }
}