1- package kotlin
2-
3- import java.util.*
4-
1+ /*
2+ * BFS
3+ */
54class Solution {
6- fun isBipartiteDfs (graph : Array <IntArray >):Boolean {
7- if (graph.isEmpty())return true
8-
9- val nodeColorMap= mutableMapOf<Int ,Color >()
10- fun dfs (node : Int ,defaultColor : Color ):Boolean {
11- if (node!in nodeColorMap.keys) nodeColorMap[node]= defaultColor
12- for (adjacentNodein graph[node]) {
13- val isEdgeVisited= nodeColorMap[adjacentNode]!= null
14- if (isEdgeVisited) {
15- val colorOfCurrentNode= nodeColorMap.getValue(node)
16- val colorOfAdjacentNode= nodeColorMap.getValue(adjacentNode)
17- if (colorOfAdjacentNode== colorOfCurrentNode)return false
18- else continue
19- }
20- if (! dfs(adjacentNode, defaultColor.inverse))return false
21- }
22- return true
23- }
24-
25- for (nodein graph.indices) {
26- if (nodein nodeColorMap.keys)continue
27- if (! dfs(node,Color .RED ))return false
28- }
29- return true
30- }
31-
32- fun isBipartiteBfs (graph : Array <IntArray >):Boolean {
5+ fun isBipartite (graph : Array <IntArray >):Boolean {
336if (graph.isEmpty())return true
347val nodeColorMap= mutableMapOf<Int ,Color >()
358
@@ -46,7 +19,8 @@ class Solution {
4619if (adjacentNodein nodeColorMap.keys) {
4720val colorOfAdjacentNode= nodeColorMap.getValue(adjacentNode)
4821if (colorOfAdjacentNode== colorOfCurrentNode)return false
49- continue
22+ continue
23+
5024 }
5125 nodeColorMap[adjacentNode]= colorOfCurrentNode.inverse
5226 queue.add(adjacentNode)
@@ -70,3 +44,87 @@ class Solution {
7044Color .GREEN -> Color .RED
7145 }
7246}
47+
48+ /*
49+ * DFS
50+ */
51+ class Solution {
52+ fun isBipartite (graph : Array <IntArray >):Boolean {
53+ if (graph.isEmpty())return true
54+
55+ val nodeColorMap= mutableMapOf<Int ,Color >()
56+ fun dfs (node : Int ,defaultColor : Color ):Boolean {
57+ if (node!in nodeColorMap.keys) nodeColorMap[node]= defaultColor
58+ for (adjacentNodein graph[node]) {
59+ val isEdgeVisited= nodeColorMap[adjacentNode]!= null
60+ if (isEdgeVisited) {
61+ val colorOfCurrentNode= nodeColorMap.getValue(node)
62+ val colorOfAdjacentNode= nodeColorMap.getValue(adjacentNode)
63+ if (colorOfAdjacentNode== colorOfCurrentNode)return false
64+ else continue
65+ }
66+ if (! dfs(adjacentNode, defaultColor.inverse))return false
67+ }
68+ return true
69+ }
70+
71+ for (nodein graph.indices) {
72+ if (nodein nodeColorMap.keys)continue
73+ if (! dfs(node,Color .RED ))return false
74+ }
75+ return true
76+ }
77+
78+ private enum class Color {RED ,GREEN }
79+
80+ private val Color .inverse
81+ get()= when (this ) {
82+ Color .RED -> Color .GREEN
83+ Color .GREEN -> Color .RED
84+ }
85+ }
86+
87+ /*
88+ * Union Find
89+ */
90+ class Solution {
91+
92+ class DSU (val n : Int ) {
93+
94+ val parent= IntArray (n) { it }
95+ val rank= IntArray (n) {1 }
96+
97+ fun find (x : Int ):Int {
98+ if (x!= parent[x])
99+ parent[x]= find(parent[x])
100+ return parent[x]
101+ }
102+
103+ fun union (x : Int ,y : Int ) {
104+ val px= find(x)
105+ val py= find(y)
106+
107+ if (rank[px]>= rank[py]) {
108+ parent[py]= px
109+ rank[px]+ = rank[py]
110+ }else {
111+ parent[px]= py
112+ rank[py]+ = rank[px]
113+ }
114+ }
115+ }
116+
117+ fun isBipartite (graph : Array <IntArray >):Boolean {
118+ val dsu= DSU (graph.size)
119+
120+ for (iin 0 until graph.size) {
121+ for (jin graph[i]) {
122+ if (dsu.find(i)== dsu.find(j))
123+ return false
124+ dsu.union(graph[i][0 ], j)
125+ }
126+ }
127+
128+ return true
129+ }
130+ }