VII.[GYM102798F]Skeleton Dynamization
神题。
首先，我们考虑若我们确定有一条边 ((u,v))，是连接层 (i) 和层 (i+1) 上对应点的边，有无办法建出整个分层图出来？
答案是有的。首先，我们先跑两遍bfs求出所有点到 (u) 和 (v) 的距离。然后，稍加观察可以发现，(1sim i) 层里的点，到 (u) 的距离更近，其余点则反之。因此我们可以根据上述算法将整张图分作两半。之后，所有处在前一半中，且与后一半中点有边的点，均来自第 (i) 层；所有处在后一半且与前一半中点有边的点均来自第 (i+1) 层。
假如我们已经确定第 (i) 层所有节点和第 (i+1) 层所有节点，则我们可以直接确定出 (i+2) 层所有节点——它们是与 (i+1) 层中点有边，且不来自 (i) 和 (i+1) 层的所有节点。类似地，我们可以确定 (i+1sim n) 层所有节点。同理，(1sim 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
",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
",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
",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
",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
",1,n);
for(int i=1;i<=n;i++)printf("%d ",i);puts("");
return 0;
}
checkedge(mnpos,mxano);
printf("%d %d
",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;
}