const Graph = require("../graph/Graph");

function BipartitionDetection($G) {
    var G = $G, colors = new Array($G.V()).fill(-1), isBipartite = true;
    var visited = new Array(G.V()).fill(false)
    var dfs = function ($v, $color) {
        visited[$v] = true;
        colors[$v] = $color;
        for (var w of G.adj($v)) {
            if (!visited[w]) {
                if (!dfs(w, 1 - $color)) return false;
            } else if (colors[w] === colors[$v]) {
                return false;
            }
        }
        return true;
    }
    for (var i = 0; i < G.V(); i++) {
        if (!visited[i]) {
            if(!dfs(i, 0)) {
                isBipartite = false;
                break;
            }
        }
    }
    this.isBipartite = function () {
        return isBipartite;
    }
}
var g = new Graph('data/二分图检测/g.txt');
var bipartitionDetection = new BipartitionDetection(g);
console.log('是不是二分图：', bipartitionDetection.isBipartite());

var g2 = new Graph('data/二分图检测/g2.txt');
var bipartitionDetection2 = new BipartitionDetection(g);
console.log('是不是二分图：', bipartitionDetection2.isBipartite());