CF1067B Multihedgehog 题解

· · 题解

Multihedgehog，刺猬图。

因为我比较懒因为我这道题是我刚学图论时做的题，连邻接矩阵都不懂，所以我莫名奇妙的高出了一种非常规操作，调了进一周结果还通过了。这篇题解我就讲一个用不到邻接矩阵的方法。

题目定义一颗“刺猬图”为：对于每一个点，出度要么为 0 要么大于等于 3。但是我存图的方法有点特殊，我分别存了每一条边的左端点（u）和右端点（v），以及每一个点都连接着几条边。是的，这成了无向图，然后我调了半天，找到了可以判断是否为刺猬树的方法：模拟“拔刺”，我们一共需要“拔”k 次，每一次先记录每个点都连接着几个度为 1 的点，我们设这个值为 d_i，如果这个图是个刺猬图，必须满足所有的 d_i 都要么是 0 要么大于等于 3。有一个 d_i 不满足就一定不是刺猬图。如果不满足就直接输出 No 即可，不用再往下执行，如果满足，就“拔刺”，将所有度为 1 的点连接着的边都删除。

最后拔完 k 次，再判断还剩几条边，如果没有边了，就说明这是个刺猬图，输出 Yes，否则输出 No。

不懂可以看代码注释：

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int u,v;//这条边连接u和v
    bool sf;//后续“拔刺”用到的，记录这根“刺”是否被“拔”了
}bian[100005];//每一条边
int dian[100005];//每一个点的度
int ci[100005];//每一个点连接着几个度为1的点
int n,k;
bool cicicici(){
    memset(ci,0,sizeof(ci));
    //找由外向内第二层的那些点，都连着几个度为1的点
    for(int i=1;i<n;i++){//分别找每条边的u和v
        if(bian[i].sf){
            //如果这个点的度为1，也就是刺猬图最外层的刺
            if(dian[bian[i].u]==1)ci[bian[i].v]++;
            if(dian[bian[i].v]==1)ci[bian[i].u]++;
        }
    }
    for(int i=1;i<=n;i++){
        if(ci[i]!=0&&ci[i]<3)return false;
        //如果有第二层的点只连了1或2个最外层的点，那么这个图就一定不是刺猬图
    }
    return true;
}
bool du(){
    memset(dian,0,sizeof(dian));
    for(int i=1;i<n;i++){//计算每个点的度
        if(bian[i].sf){
            dian[bian[i].u]++;
            dian[bian[i].v]++;
        }
    }
    return cicicici();
}
void baci(){//拔刺
    for(int i=1;i<n;i++){
        if(bian[i].sf){
            if(dian[bian[i].u]==1||dian[bian[i].v]==1){
                //如果连着度为1的点就把这条边删除
                bian[i].sf=false;
            }
        }
    }
    return;
}
int diandian(){
    int cnt=0;
    for(int i=1;i<n;i++){
        if(bian[i].sf)cnt++;//还有几条边
    }
    return cnt;
}
void no(){cout<<"No\n";exit(0);}//压行用的
void yes(){cout<<"Yes\n";exit(0);}
int main(){
    cin>>n>>k;
    if(k>12||n==1)no();//3^13>10^4
    for(int i=1;i<n;i++){
        cin>>bian[i].u>>bian[i].v;
        bian[i].sf=true;
    }
    if(!du())no();//先判断一遍
    for(int i=1;i<=k;i++){//需要拔k次刺
        baci();
        if(!du())no();
        else if(i==k&&diandian()==0)yes();
        if(diandian()==0)no();
    }
    no();
    return 0;
}