二分図の判定(図の探索)

2314 ワード

  • タイトル説明:n個の頂点を有する図を与える.図上の各頂点を染色し、隣接する頂点の色を異にします.最大2色まで染色しますか?タイトルは重辺と自環がないことを保証します.(1<=n<=1000)
  • コード:
  • #include
    #include
    using namespace std;
    const int MAX_N=1e2+6;
    vector<int>G[MAX_N];
    int V,color[MAX_N];
    bool dfs(int v,int c){
        color[v]=c;
        for(int i=0;iif(color[G[v][i]]==c)return false;
            if(color[G[v][i]]==0&&!dfs(G[v][i],-c))return false;
        }
        return true;
    }
    void solve(){
        for(int i=0;iif(color[i]==0)
                if(!dfs(i,1)){
                    cout<<"No"<return ;
                }
        }
        cout<<"Yes"<int main(){
        ios::sync_with_stdio(false);cin.tie(0);
        cin>>V;
        solve();
    }