-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTwoColor.java
More file actions
34 lines (32 loc) · 793 Bytes
/
TwoColor.java
File metadata and controls
34 lines (32 loc) · 793 Bytes
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
package Graph.dfs;
import Graph.Graph;
/*是否是二分图即每条边的两个端点的颜色都不相同*/
public class TwoColor {
boolean isTwoColor=true;
boolean book[];
boolean color[];
public TwoColor( Graph g){
book=new boolean[g.V()];
color=new boolean[g.V()];
for(int i=0;i<g.V();i++){
if(!book[i])
dfs(g,i);
}
}
public void dfs(Graph g,int v){
book[v]=true;
for(int i: g.adj(v)){
if(!book[i]){
color[i]=!color[v];
dfs(g,i);
}
else
if(color[i]==color[v]){
isTwoColor=false;
}
}
}
public boolean isBipartite(){
return isTwoColor;
}
}