Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitff116c7

Browse files
add a solution for 785
1 parent6144fd5 commitff116c7

File tree

2 files changed

+46
-4
lines changed

2 files changed

+46
-4
lines changed

‎src/main/java/com/fishercoder/solutions/_785.java

Lines changed: 38 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
importjava.util.LinkedList;
44
importjava.util.Queue;
5+
importjava.util.Stack;
56

67
publicclass_785 {
78
publicstaticclassSolution1 {
@@ -11,7 +12,7 @@ public static class Solution1 {
1112
publicbooleanisBipartite(int[][]graph) {
1213
int[]visited =newint[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
1516
for (inti =0;i <graph.length;i++) {
1617
if (graph[i].length !=0 &&visited[i] ==0) {
1718
visited[i] =1;
@@ -21,6 +22,7 @@ public boolean isBipartite(int[][] graph) {
2122
intcurrent =queue.poll();
2223
for (intnode :graph[current]) {
2324
if (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)
2426
visited[node] = (visited[current] ==1) ?2 :1;
2527
queue.offer(node);
2628
}else {
@@ -35,4 +37,39 @@ public boolean isBipartite(int[][] graph) {
3537
returntrue;
3638
}
3739
}
40+
41+
publicstaticclassSolution2 {
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+
publicbooleanisBipartite(int[][]graph) {
49+
//0 means uncolored, 1 means red and 2 means blue
50+
int[]colors =newint[graph.length];
51+
for (intstart =0;start <graph.length;start++) {
52+
if (colors[start] ==0) {
53+
Stack<Integer>stack =newStack<>();
54+
stack.push(start);
55+
colors[start] =1;//color it to be red
56+
57+
while (!stack.isEmpty()) {
58+
Integercurr =stack.pop();
59+
for (intneighbor :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+
}elseif (colors[neighbor] ==colors[curr]) {
65+
//this means the two connected nodes have the same color, so this is not a bipartite
66+
returnfalse;
67+
}
68+
}
69+
}
70+
}
71+
}
72+
returntrue;
73+
}
74+
}
3875
}

‎src/test/java/com/fishercoder/_785Test.java

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,29 +5,34 @@
55
importorg.junit.BeforeClass;
66
importorg.junit.Test;
77

8-
importstaticorg.junit.Assert.assertEquals;
8+
importstaticorg.junit.Assert.assertFalse;
9+
importstaticorg.junit.Assert.assertTrue;
910

1011
publicclass_785Test {
1112
privatestatic_785.Solution1solution1;
13+
privatestatic_785.Solution2solution2;
1214
privatestaticint[][]graph;
1315

1416
@BeforeClass
1517
publicstaticvoidsetup() {
1618
solution1 =new_785.Solution1();
19+
solution2 =new_785.Solution2();
1720
graph =newint[][]{};
1821
}
1922

2023
@Test
2124
publicvoidtest1() {
2225
graph =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,2,3],[0,2],[0,1,3],[0,2]");
2326
CommonUtils.print2DIntArray(graph);
24-
assertEquals(false,solution1.isBipartite(graph));
27+
assertFalse(solution1.isBipartite(graph));
28+
assertFalse(solution2.isBipartite(graph));
2529
}
2630

2731
@Test
2832
publicvoidtest2() {
2933
graph =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,3],[0,2],[1,3],[0,2]");
3034
CommonUtils.print2DIntArray(graph);
31-
assertEquals(true,solution1.isBipartite(graph));
35+
assertTrue(solution1.isBipartite(graph));
36+
assertTrue(solution2.isBipartite(graph));
3237
}
3338
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp