二分图染色法

定义：一个无向图G是二部图当且仅当G中无奇数长度的回路

二分图相关：二分图的最大匹配、完美匹配和匈牙利算法

我们利用染色法来判断一个图是不是二分图，先找一个点为起点，然后把与它相连的点的颜色都变成与它相反的颜色,然后把这些点加入到队列中，如果这些点的颜色与父节点的不一样，就忽略，如果一样就证明了这个图不是二分图

NYOJ1015 二部图(染色法判断二分图)

const int N=200+20;
vector<int> G[N];
int color[N];
int bfs()
{
    queue<int>q;
    q.push(0);
    color[0]=1;
    while(!q.empty())
    {
        int v1=q.front();
        q.pop();
        for(int i=0; i<G[v1].size(); i++)
        {
            int v2=G[v1][i];
            if(color[v2]==-1)
            {
                color[v2]=-color[v1];
                q.push(v2);
            }
            else if(color[v1]==color[v2])
                return 0;
        }
    }
    return 1;
}
int main()
{
    int n,m,a,b;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<N; i++)G[i].clear();
        mem(color,-1);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        if(bfs())
            puts("BICOLORABLE.");
        else
            puts("NOT BICOLORABLE.");
    }
    return 0;
}

Codeforces Round #435 (Div. 2)B. Mahmoud and Ehab and the bipartiteness(二分图，染色法)

题目给了一棵树，问的是需要添加多少条边,问现在最多可以添加多少条边使得这个图中不存在自环，重边，并且此图还是一个二分图.

可以用染色法染色，求出对应的两个点集数量a和b，那么他们的最大有ab条边，那么答案就是：a\b-(n-1)条边

const ll N=1e5+20;  
vector<ll>G[N];  
ll color[N],vis[N];  
void dfs(ll rt)  
{  
    vis[rt]=1;  
    if(color[rt]==0)  
        color[rt]=1;  
    for(ll i=0; i<G[rt].size(); i++)  
    {  
        ll v=G[rt][i];  
        if(!vis[v])  
        {  
            if(color[rt]==1)  
                color[v]=2;  
            else  
                color[v]=1;  
            vis[v]=1;  
            dfs(v);  
        }  
    }  
}  
int main()  
{  
    ll n,x,y;  
    scanf("%lld",&n);  
    for(ll i=0; i<n-1; i++)  
    {  
        scanf("%lld%lld",&x,&y);  
        G[x].push_back(y);  
        G[y].push_back(x);  
    }  
    dfs(1);  
    ll a=0,b=0;  
    for(ll i=1; i<=n; i++)  
        if(color[i]==1)  
            a++;  
        else  
            b++;  
    printf("%lld\n",a*b-(n-1));  
    return 0;  
}