src/graph/is_bipartite.hpp

View this file on GitHub
Last update: 2026-01-07 21:13:29+09:00
Include: #include "src/graph/is_bipartite.hpp"

Depends on

src/template.hpp

Code

#pragma once
#include "../template.hpp"
pair<bool,vector<int>> is_bipartite(vector<vector<int>> &G){
    int N=si(G);
    vector<int> color(N,-1);
    bool isb=1;
    auto dfs=[&](auto dfs,int v)->void {
        for(int e: G[v]){
            if(~color[e]){
                isb&=(color[v]!=color[e]);
            }
            else {
                color[e]=color[v]^1;
                dfs(dfs,e);
            }
        }
    };
    rep(i,N){
        if(~color[i]) continue;
        color[i]=0;
        dfs(dfs,i);
    }
    return {isb,color};
}

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/graph/is_bipartite.hpp"
pair<bool,vector<int>> is_bipartite(vector<vector<int>> &G){
    int N=si(G);
    vector<int> color(N,-1);
    bool isb=1;
    auto dfs=[&](auto dfs,int v)->void {
        for(int e: G[v]){
            if(~color[e]){
                isb&=(color[v]!=color[e]);
            }
            else {
                color[e]=color[v]^1;
                dfs(dfs,e);
            }
        }
    };
    rep(i,N){
        if(~color[i]) continue;
        color[i]=0;
        dfs(dfs,i);
    }
    return {isb,color};
}