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;
        }
    }
}
上一篇下一篇

猜你喜欢

热点阅读