@@ -4,23 +4,35 @@ public boolean isBipartite(int[][] graph) {
44int []color =new int [n ];
55Arrays .fill (color , -1 );
66for (int i =0 ;i <n ;i ++) {
7- if (color [i ] == -1 ) {
8- Stack <Integer >stack =new Stack <>();
9- stack .push (i );
10- color [i ] =0 ;
11- while (!stack .isEmpty ()) {
12- Integer node =stack .pop ();
13- for (Integer neighbor :graph [node ]) {
14- if (color [neighbor ] == -1 ) {
15- stack .push (neighbor );
16- color [neighbor ] =color [node ] ^1 ;
17- }
18- else if (color [neighbor ] ==color [node ]) {
19- return false ;
20- }
7+ if (color [i ] == -1 && !bipartiteCheck (graph ,i ,color )) {
8+ return false ;
9+ }
10+ }
11+ return true ;
12+ }
13+
14+ private boolean bipartiteCheck (int [][]graph ,int node ,int []color ) {
15+ Queue <Integer >queue =new LinkedList <>();
16+ queue .add (node );
17+ int currColor =0 ;
18+ while (!queue .isEmpty ()) {
19+ int size =queue .size ();
20+ while (size -- >0 ) {
21+ int removed =queue .remove ();
22+ if (color [removed ] != -1 ) {
23+ if (color [removed ] !=currColor ) {
24+ return false ;
25+ }
26+ continue ;
27+ }
28+ color [removed ] =currColor ;
29+ for (int conn :graph [removed ]) {
30+ if (color [conn ] == -1 ) {
31+ queue .add (conn );
2132 }
2233 }
2334 }
35+ currColor =currColor ==1 ?0 :1 ;
2436 }
2537return true ;
2638 }