VII.[GYM102798F]Skeleton Dynamization
神题。
首先,我们考虑若我们确定有一条边 \((u,v)\),是连接层 \(i\) 和层 \(i+1\) 上对应点的边,有无办法建出整个分层图出来?
答案是有的。首先,我们先跑两遍bfs求出所有点到 \(u\) 和 \(v\) 的距离。然后,稍加观察可以发现,\(1\sim i\) 层里的点,到 \(u\) 的距离更近,其余点则反之。因此我们可以根据上述算法将整张图分作两半。之后,所有处在前一半中,且与后一半中点有边的点,均来自第 \(i\) 层;所有处在后一半且与前一半中点有边的点均来自第 \(i+1\) 层。
假如我们已经确定第 \(i\) 层所有节点和第 \(i+1\) 层所有节点,则我们可以直接确定出 \(i+2\) 层所有节点——它们是与 \(i+1\) 层中点有边,且不来自 \(i\) 和 \(i+1\) 层的所有节点。类似地,我们可以确定 \(i+1\sim n\) 层所有节点。同理,\(1\sim i-1\) 层的节点也可以类似确定。如此确定后,只需check此分层图是否符合要求即可(层层间仅所有对应点有且仅有一条边;每层的图同构)。至于如何check图同构,因为同构的点都已经对应了,直接check度数是否相等即可。
考虑上述算法的复杂度——其全程只进行了对点和边的遍历,复杂度为 \(O(n+m)\)。于是我们下面需要找到一种合适的枚举边 \((u,v)\) 的方式。
显然,对于一个点,其必有一条边连到下一层中某个点。这意味着,我们可以通过遍历与一点相邻的所有边check进而check所有的划分方式。
考虑所有点中度数最少的点——这一值最大是 \(O(\sqrt{m})\) 级别的——我们枚举其所有边check,最大复杂度为 \(\Big((n+m)\sqrt{m}\Big)\),可以通过。
需要注意的是,度数最少的点一定是位于分层图中的第一层或最后一层中(但实际上可以直接将其当作是在第一层),故善用这一性质可以减少很多讨论量。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int n,m,dis1[N],dis2[N],lay[N],num,deg[N],mnpos,mxano,mxlay,pre[N];
queue<int>q;
vector<int>v[N];
void bfs(int S,int *d){
q.push(S),d[S]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(auto y:v[x])if(d[y]==-1)d[y]=d[x]+1,q.push(y);
}
}
vector<int>r[N];
void functionset(int id){
num++;
for(auto x:r[id])for(auto y:v[x])if(!lay[y])lay[y]=num,r[num].push_back(y);else if(lay[y]==lay[x])deg[x]++;
if(r[num].empty())num--;
}
bool checkedge(int U,int V){
for(int i=1;i<=num;i++)r[i].clear();num=2;
// printf("%d\n",V);
memset(dis2,-1,sizeof(dis2)),bfs(V,dis2),memset(lay,0,sizeof(lay)),memset(deg,0,sizeof(deg));
// for(int i=1;i<=n;i++)printf("%d ",dis1[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",dis2[i]);puts("");
for(int x=1;x<=n;x++){
// printf("%d:%d %d\n",x,dis1[x],dis2[x]);
if(dis1[x]==dis2[x])return false;
for(auto y:v[x]){
if((dis1[x]<dis2[x])==(dis1[y]<dis2[y]))continue;
if(dis1[x]<dis2[x])r[lay[x]=1].push_back(x);
else r[lay[x]=2].push_back(x);
}
}
for(int i=1;i<=num;i++)functionset(i);
// for(int i=1;i<=n;i++)printf("%d ",lay[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",deg[i]);puts("");
for(int i=1;i<=num;i++)for(auto x:r[i]){
int pr=0,nx=0;
for(auto y:v[x]){
if(lay[y]==lay[x])continue;
if(lay[y]==lay[x]+1){
if(!nx)nx=y;
else return false;
continue;
}
if(lay[y]==lay[x]-1){
if(!pr)pr=y;
else return false;
continue;
}
return false;//has a connetion beyond adjacent layers
}
// printf("%d->%d->%d\n",pr,x,nx);
if(lay[x]<num&&(!nx||deg[nx]!=deg[x]))return false;
if(lay[x]>1&&(!pr||deg[pr]!=deg[x]))return false;
if(lay[x]>1)pre[x]=pre[pr];
else pre[x]=x;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x),deg[x]++,deg[y]++;
mnpos=1;
for(int i=2;i<=n;i++)if(deg[i]<deg[mnpos])mnpos=i;
// printf("%d\n",mnpos);
memset(dis1,-1,sizeof(dis1)),bfs(mnpos,dis1);
for(auto x:v[mnpos]){
if(!checkedge(mnpos,x))continue;
if(mxlay<num)mxlay=num,mxano=x;
}
if(!mxlay){
printf("%d %d\n",1,n);
for(int i=1;i<=n;i++)printf("%d ",i);puts("");
return 0;
}
checkedge(mnpos,mxano);
printf("%d %d\n",mxlay,n/mxlay);
for(int i=1;i<=mxlay;i++){
sort(r[i].begin(),r[i].end(),[](int x,int y){return pre[x]<pre[y];});
for(auto j:r[i])printf("%d ",j,pre[j]);
puts("");
}
return 0;
}