Is Graph Bipartite?
2018-06-27 本文已影响3人
Frank_Kivi
https://www.lintcode.com/problem/is-graph-bipartite/description
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
/**
* @param graph: the given undirected graph
* @return: return true if and only if it is bipartite
*/
public boolean isBipartite(int[][] graph) {
// Write your code here
List<Edge> list = new ArrayList<>();
for (int i = 0; i < graph.length; i++) {
int[] ints = graph[i];
for (int j = 0; j < ints.length; j++) {
int anInt = ints[j];
list.add(new Edge(i, anInt));
}
}
Set<Integer> a = new HashSet<>();
Set<Integer> b = new HashSet<>();
for (int i = 0; i < list.size(); i++) {
Edge edge = list.get(i);
if (a.contains(edge.left)) {
if (a.contains(edge.right)) {
return false;
}
}
if (b.contains(edge.left) && b.contains(edge.right)) {
return false;
}
if (a.contains(edge.left)) {
b.add(edge.right);
} else if (a.contains(edge.right)) {
b.add(edge.left);
} else if (b.contains(edge.left)) {
a.add(edge.right);
} else if (b.contains(edge.right)) {
a.add(edge.left);
} else {
a.add(edge.left);
b.add(edge.right);
}
}
return true;
}
private class Edge {
int left;
int right;
public Edge(int left, int right) {
this.left = left;
this.right = right;
}
}
}