22
33import java .util .LinkedList ;
44import java .util .Queue ;
5+ import java .util .Stack ;
56
67public class _785 {
78public static class Solution1 {
@@ -11,7 +12,7 @@ public static class Solution1 {
1112public boolean isBipartite (int [][]graph ) {
1213int []visited =new int [graph .length ];
1314//BFS
14- //0 means never encountered before, 1 meanstraversing in progress , 2 meanstraversing completed
15+ //0 means never encountered before, 1 meanswe put this node into set A , 2 meanswe put this node into set B
1516for (int i =0 ;i <graph .length ;i ++) {
1617if (graph [i ].length !=0 &&visited [i ] ==0 ) {
1718visited [i ] =1 ;
@@ -21,6 +22,7 @@ public boolean isBipartite(int[][] graph) {
2122int current =queue .poll ();
2223for (int node :graph [current ]) {
2324if (visited [node ] ==0 ) {
25+ //if the current node is in set A (1), then we put its neighbor in set B (2), otherwise set A (1)
2426visited [node ] = (visited [current ] ==1 ) ?2 :1 ;
2527queue .offer (node );
2628 }else {
@@ -35,4 +37,39 @@ public boolean isBipartite(int[][] graph) {
3537return true ;
3638 }
3739 }
40+
41+ public static class Solution2 {
42+ /**
43+ * credit: https://leetcode.com/problems/is-graph-bipartite/solution/
44+ * <p>
45+ * Let red indicate set A and blue indicate set B, if the graph is a bipartite,
46+ * we should be able to greedily color this graph: for each node, if we color it red, then color all of its neighbors blue, etc.
47+ */
48+ public boolean isBipartite (int [][]graph ) {
49+ //0 means uncolored, 1 means red and 2 means blue
50+ int []colors =new int [graph .length ];
51+ for (int start =0 ;start <graph .length ;start ++) {
52+ if (colors [start ] ==0 ) {
53+ Stack <Integer >stack =new Stack <>();
54+ stack .push (start );
55+ colors [start ] =1 ;//color it to be red
56+
57+ while (!stack .isEmpty ()) {
58+ Integer curr =stack .pop ();
59+ for (int neighbor :graph [curr ]) {
60+ if (colors [neighbor ] ==0 ) {
61+ stack .push (neighbor );
62+ //if the current node is red (1), then we color it to be blue (2), otherwise red (1)
63+ colors [neighbor ] = (colors [curr ] ==1 ) ?2 :1 ;
64+ }else if (colors [neighbor ] ==colors [curr ]) {
65+ //this means the two connected nodes have the same color, so this is not a bipartite
66+ return false ;
67+ }
68+ }
69+ }
70+ }
71+ }
72+ return true ;
73+ }
74+ }
3875}