Graph implementations

bipartite.cpp

typedef vector<vector<int>> graph;
graph create(int n, vector<vector<int>> &edges) {

    graph adj(n, vector<int>(0));
    for(auto e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    return adj;
}

bool check_bipartite(graph &adj, vector<int> &vis, int idx) {

    queue<int> q;

    vis[idx] = 0;
    q.push(idx);

    while(!q.empty()) {
        int v = q.front();
        q.pop();

        for(int x: adj[v]) {
            /* give alternate color and push in queue */
            if(vis[x] == -1) {
                vis[x] = 1 - vis[v];
                q.push(x);
            }

            /* not bipartite if same color */
            if(vis[v] == vis[x])
                return false;
        }
    }

    return true;
}

int find_unvisited(vector<int> &vis) {
    int idx = -1;
    for(int i=0; i<vis.size(); i++) 
        if(vis[i] == -1) {
            idx = i;
            break;
        }
    return idx;
}

int solve(int A, vector<vector<int> > &B) {
    
    auto adj = create(A, B);
    
    /* -1, 0(red), 1(black) */
    vector<int> vis(adj.size(), -1);

    // keep checking till nodes are colored
    bool ans = true;
    int idx = find_unvisited(vis);
    while(idx > -1) {
        ans = ans && check_bipartite(adj, vis, idx);
        if(ans == false)
            return 0;
        idx = find_unvisited(vis);
    }
    
    return 1;
}