Codeforces Round 863 (Div. 3) F - Is It Flower?

· · 题解

题目大意

首先定义花：

一朵 n 阶的花就是由一个 n 边形（n>2），在每个顶点上再拓展一个 n 边形所构成的图形。

这是一个 3 阶的花。

给你一个图，问你它是不是一朵花。

每个点有 T 组多测数据。

解题思路

首先很容易知道，这张图上只会有两种点，一种度为 2，一种度为 4。那么我们在建图的时候就可以判断某些图是否是花。

然后又很容易想到如果一张图是花，那么度为 4 的点一定是中间的那 n 个点，那么我们就可以统计一下这种点的数量，这就是这个可能的花的阶数。其他的点因为每 n-1 个就对应着一个中间多边形的点，所以显然 cnt3=cnt4\times (cnt4-1)，此处 cnt3 表示度为 2 的点的个数，cnt4 表示度为 4 的点的个数。

接下来便是从中间的 n 个点入手。首先这 n 个点一定要是成一个环，并且环上每个不相邻的点之间不能直接联通。做完这一步之后我们再从这些点出发，找长度同样为 n，但是其他节点的度皆为 2 的环，要求和前一步一样，环上每个不相邻的点之间不能直接联通。如果不满足这些条件那这张图一定不是花，否则就是花。

一些建议

虽然各位都是神犇，但是在清空图的时候还是要小心，注意数据组数和范围。

AC 代码

DEBUG 部分因为错的太频繁，所以调了一下，有点丑，还请见谅。

#define ll long long
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define F first
#define S second
#define DEBUG
using namespace std;
const int N=2e5+5;
int t,n,m,u,v;
vector<int> e[N],q;
map<int,int> mp;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) e[i].clear();
        mp.clear();
        q.clear();
        for(int i=1;i<=m;++i){
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        for(int i=1;i<=n;++i){
            ++mp[e[i].size()];
        }
        #ifdef DEBUG
        printf("%d\n",mp.size());
        #endif
        if(mp.size()!=2){
            printf("NO\n");
            continue;
        }
        int cnt[5]={0,0,0},pos,fa=0;
        for(pii to:mp){
            cnt[++cnt[0]]=to.F;
            cnt[cnt[0]+2]=to.S;
        }
        if(2*cnt[1]!=cnt[2] || cnt[3]!=cnt[4]*cnt[4]-cnt[4] || cnt[1]!=2){
            #ifdef DEBUG
            printf("%d %d %d %d\n",cnt[1],cnt[2],cnt[3],cnt[4]);
            #endif
            printf("NO\n");
            continue;
        }
        for(int i=1;i<=n;++i){
            if(e[i].size()==cnt[2]){
                pos=i;
                break;
            }
        }
        bool flag=0;
        q.push_back(pos);
        for(int i=1;i<=cnt[4];++i){
            #ifdef DEBUG
            printf("%d | ",pos);
            #endif
            for(int to:e[pos]){
                if(e[to].size()==cnt[2] && fa!=to){
                    #ifdef DEBUG
                    printf("%d ",to);
                    #endif
                    fa=pos;
                    pos=to;
                    if(i!=cnt[4]) q.push_back(to);
                    break;
                }
            }
            #ifdef DEBUG
            puts("");
            #endif
            if(pos==q[0] && i!=cnt[4]){
                flag=1;
                break;
            }
        }
        #ifdef DEBUG
        for(int p:q) printf("%d ",p);
        puts("");
        #endif
        if(pos!=q[0] || flag || q.size()!=cnt[4]){
            printf("NO\n");
            continue;
        }
        for(int p:q){
            fa=0;
            int cc=0;
            pos=p;
            for(int i=1;i<cnt[4];++i){
                #ifdef DEBUG
                printf("%d ",pos);
                #endif
                for(int to:e[pos]){
                    if(e[to].size()==cnt[1] && fa!=to){
                        fa=pos;
                        pos=to;
                        ++cc;
                        break;
                    }
                }
                if(pos==p){
                    flag=1;
                    break;
                }
            }
            #ifdef DEBUG
            printf("%d\n",pos);
            #endif
            if(flag) break;
            for(int to:e[pos]){
                if(e[to].size()==cnt[2] && fa!=to){
                    fa=pos;
                    pos=to;
                    break;
                }
            }
            if(pos!=p || flag || cc!=cnt[4]-1){
                flag=1;
                break;
            }
        }
        if(flag){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
    }
    return 0;
}

代码很长，但是还请不要偷懒，毕竟这份代码也交不了（偷笑）。