题解 P4429 【[BJOI2018]染色】

· · 题解

这是一道结论题

我的心路历程是这样的

显然奇环是NO

否则的话，我注意到一个偶环是可以钦定两个连续的点的颜色的

对于长度为4的偶环可以 :AB AB BC AC

这样我们可以发现如果两个偶环没交，答案是NO

我们可以对于每一个联通块，考虑点数和边数的大小关系

n<m n=m都是YES

n>=m+2 可以发现总有两个相交的偶环，所以是NO

我特别naive地交了一个直接判断n>m的程序，发现爆成10分（比赛数据）

事实上n=m+1比较复杂

我们可以发现当环有交时，一定是两个点度数为3,也就是两个点直接有3条路径（忽略度数为1的点）

再次给出结论，只有两个点直接路径为2-2-偶数时是yes，1-3-3，2-4-4均是no

具体构造是：1-3-3:两个度数为3的点均为AB，别的两条有点路径为AB/AC/BC, AB/BC/AC

2-4-4:点数为3的路径为AB,AB,AB 别的是AB BC CD DB AB/AB AC CD DA AB

可以发现再增加点数仍然可以构造出不合法解

最后结论：

1:奇环->NO

2:讨论 点数n和边数m的关系 n<=m->YES

n>m+1->NO

n=m+1讨论一下三条路径的长度情况，具体实现可以使用拓扑排序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
    int x = 0; char ch = gc(); bool positive = 1;
    for (; !isdigit(ch); ch = gc()) if (ch == '-')  positive = 0;
    for (; isdigit(ch); ch = gc())  x = x * 10 + ch - '0';
    return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
        a=-a; putchar('-');
    }
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
        a=-a; putchar('-');
    }
    write(a); puts("");
}
inline int rnd(int x){
    return rand()%x;
}
inline ull rnd(){
    return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=10005;
int n,m,V,E,flag,color[N],rd[N];
queue<int> q;
vector<int> v[N],jb;
void dfs(int p,int dq){
    if(flag)return;
    if(color[p]!=-1){if(color[p]!=dq){flag=1; puts("NO"); } return;}
    color[p]=dq; V++; E+=v[p].size();
    jb.push_back(p);
    for(unsigned i=0;i<v[p].size();i++){
        dfs(v[p][i],dq^1);
    }
}
int main(){
    int T=read();
    while(T--){
        n=read(); m=read(); flag=0; memset(color,-1,sizeof(color));
        for(int i=1;i<=n;i++)v[i].clear();
        for(int i=1;i<=m;i++){
            int s=read(),t=read();
            v[s].push_back(t); v[t].push_back(s);
        }
        for(int i=1;i<=n;i++)if(color[i]==-1){
            V=E=0; jb.clear(); dfs(i,0); if(flag)break; if(E/2>V+1){puts("NO"); flag=1; break;}
            if(E/2<=V)continue;
            for(unsigned j=0;j<jb.size();j++){
                rd[jb[j]]=v[jb[j]].size(); if(v[jb[j]].size()==1)q.push(jb[j]);
            }
            while(!q.empty()){
                int t=q.front(); q.pop();
                for(unsigned j=0;j<v[t].size();j++)if(--rd[v[t][j]]==1)q.push(v[t][j]);
            }
            int ttt=0;

            for(unsigned j=0;j<jb.size();j++)if(rd[jb[j]]==2){
                int gao=0;
                for(unsigned k=0;k<v[jb[j]].size();k++)if(rd[v[jb[j]][k]]==3)gao++;
                if(gao==2){ttt++;}
            }
            if(ttt<2){
                puts("NO"); flag=1; break;
            }
        }
        if(!flag)puts("YES");
    }
}