P10829 题解

· · 题解

Problem Link

题目大意

定义一个图是好的，当且仅当图上恰有一个点，或可以由三个大小相等的好图各选出一个点连出三元环得到。

给定一个 n 个点 m 条边的无向图，判定该图是否是好的。

数据范围：n\le 2\times 10^5,m\le 3\times 10^5。

思路分析

考虑如何刻画好的图，在无向图上不好处理问题，注意到这张图是边仙人掌，可以建出圆方树。

那么原图上的每个环对应一个方点，最特殊的显然是最后一次加入的环，即某个方点删去后整棵树变成大小相同的三部分，且每部分都是好的。

那么这个方点显然就是圆方树的重心，容易证明一张图是好的当且仅当其圆方树的点分树是完美三叉树。

实现的时候可以在建圆方树时直接判断每个边双联通分量大小是否为 3，点分治的时候要维护一下深度方便判定大小相等。

时间复杂度 \mathcal O(n+m)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
int n,m,tot,dfn[MAXN],low[MAXN],dcnt,stk[MAXN],tp;
vector <int> G[MAXN],E[MAXN];
void link(int u,int v) { E[u].push_back(v),E[v].push_back(u); }
void tarjan(int u) {
    dfn[u]=low[u]=++dcnt,stk[++tp]=u;
    for(int v:G[u]) {
        if(!dfn[v]) {
            tarjan(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) {
                int k,c=1; link(u,++tot);
                do ++c,link(k=stk[tp--],tot); while(k^v);
                if(c!=3) puts("ne"),exit(0);
            }
        } else low[u]=min(low[u],dfn[v]);
    }
}
int qk(int x) {
    int c=0;
    for(;x>1;x/=3,++c) if(x%3) puts("ne"),exit(0);
    return c;
}
int siz[MAXN],cur[MAXN];
bool vis[MAXN];
bool dfs1(int u,int k) {
    int cnt=0; vis[u]=true;
    for(int v:E[u]) cnt+=!vis[v];
    if(cnt!=(k?3:0)) puts("ne"),exit(0);
    function<void(int,int)> dfs2=[&](int x,int fz) {
        siz[x]=1;
        for(int y:E[x]) if(!vis[y]&&y!=fz) dfs2(y,x),siz[x]+=siz[y];
    };
    dfs2(u,0);
    for(int v:E[u]) if(!vis[v]) {
        int rt=0,mx=siz[v];
        function<void(int,int)> dfs3=[&](int x,int fz) {
            cur[x]=mx-siz[x];
            for(int y:E[x]) if(!vis[y]&&y!=fz) dfs3(y,x),cur[x]=max(cur[x],siz[y]);
            if(!rt||cur[x]<cur[rt]) rt=x;
        };
        dfs3(v,u);
        if(!dfs1(rt,k-1)) puts("ne"),exit(0);
    }
    return true;
}
signed main() {
    scanf("%d%d",&n,&m),tot=n;
    for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    for(int i=1;i<=n;++i) {
        sort(G[i].begin(),G[i].end());
        if(unique(G[i].begin(),G[i].end())!=G[i].end()) return puts("ne"),0;
    }
    tarjan(1);
    for(int i=1;i<=n;++i) if(!dfn[i]) return puts("ne"),0;
    int rt=0,mx=tot;
    function<void(int,int)> dfs3=[&](int x,int fz) {
        siz[x]=1;
        for(int y:E[x]) if(!vis[y]&&y!=fz) dfs3(y,x),cur[x]=max(cur[x],siz[y]),siz[x]+=siz[y];
        cur[x]=max(cur[x],mx-siz[x]);
        if(!rt||cur[x]<cur[rt]) rt=x;
    };
    dfs3(1,0);
    puts(dfs1(rt,qk(n))?"da":"ne");
    return 0;
}