C++二分圖代碼實現(xiàn)

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAX 10000

vector<int> G[MAX];
int color[MAX];

void buildGraph()
{
    int e;
    scanf("%d",&e);
    int s,t;
    for(int i=0;i<e;i++)

    {
        scanf("%d %d",&s,&t);
        //printf("s=%d,t=%d,i=%d",s,t,i);
        G[s].push_back(t);
        G[t].push_back(s);
    }
}

bool dfs(int v,int c)
{
    color[v]=c;
    for(int i=0;i<G[v].size();i++)
    {
        if(color[G[v][i]]==0)
        {
            return dfs(G[v][i],-c);
        }
        if(color[G[v][i]]==c)
        {
            return false;
        }
    }
    return true;
}

void solve(int v)
{
    for(int i=0;i<v;i++)
    {
        if(color[i]==0)
        {
            if(!dfs(i,1))
            {
                printf("no!\n");
                return;
            }

        }
    }
    printf("yes!\n");
}

int main()
{
    buildGraph();
    solve(3);
    return 0;
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容