题解 P1330 【封锁阳光大学】

树上的男爵 · 2017-08-14 18:35:58 · 题解

二分染色法吧 利用DFS

下面是挑战白书上的模板，基本和题目差不多，

//! 因为不确定是不是 连通图 所以要将所有点枚举一遍

//! 如果已经确定是连通图 那就只需要任取一个点进行

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10001
vector<int>G[MAXN];
int V;//! 顶点个数
int color[MAXN];//!记录顶点的颜色
bool DFS(int v,int c)
{
    color[v]=c;
    for(int i=0;i<G[v].size();i++)
    {
        //!  如果出现相邻点颜色相同  那么就返回false
        if(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;i<V;i++)
    {
        if(color[i]==0)//!  这个点还没有染色
        {
            if(!DFS(i,1))//!  那么就染成1，然后进行判断，如果不能达成条件,就只跳出不用管其他了
            {printf("No\n");return ;}
        }
    }
    printf("Yes\n");
}