考虑对于第$i$层$x$与第$i+1$层所对应的点$y$，点$p$在前$i$层中当且仅当$p$到$x$比$p$到$y$距离小
由此，考虑枚举第一层的一个点以及对应到第二层的边，通过bfs就可以确定第一层的点
接下来，标记第一层的点后，第一层的点剩下到未标记的点即为第二层的点，以此类推，就可以$o(m)$的确定所有点（注意还要判断）
（其实判定是$o(m\log m)$的，需要用map每一层内部的边，所以需要一定常数优化）
注意到度数最小的点，必然出现在第一层或最后一层（否则第一层或最后一层对应的点度数少1），根据对称性，不难证明对于任意一个度数最少的点，存在一组方案满足其在第一层中
同时，度数最小的点的度数不超过$\min(\frac{m}{n},n)$，即$o(\sqrt{m})$，总复杂度为$o(m\sqrt{m})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 struct ji{ 5 int nex,to; 6 }edge[N<<2]; 7 queue<int>q; 8 vector<int>v[N],ve[N],ansv[N]; 9 int E,n,m,x,y,ans,head[N],r[N],d[N],d0[N],vis[N],pos[N]; 10 void add(int x,int y){ 11 edge[E].nex=head[x]; 12 edge[E].to=y; 13 head[x]=E++; 14 } 15 void bfs(int k){ 16 memset(d,0x3f,sizeof(d)); 17 d[k]=0; 18 q.push(k); 19 while (!q.empty()){ 20 int k=q.front(); 21 q.pop(); 22 for(int i=head[k];i!=-1;i=edge[i].nex) 23 if (d[edge[i].to]==0x3f3f3f3f){ 24 d[edge[i].to]=d[k]+1; 25 q.push(edge[i].to); 26 } 27 } 28 } 29 bool check(){ 30 if (n%v[1].size())return 0; 31 if ((m-(n-v[1].size()))%(n/v[1].size()))return 0; 32 memset(vis,0,sizeof(vis)); 33 for(int i=0;i<v[1].size();i++)pos[v[1][i]]=i; 34 for(int i=1;i<n/v[1].size();i++){ 35 for(int j=0;j<v[i].size();j++)vis[v[i][j]]=1; 36 v[i+1].clear(); 37 for(int j=0;j<v[i].size();j++){ 38 int to=0; 39 for(int k=head[v[i][j]];k!=-1;k=edge[k].nex) 40 if (!vis[edge[k].to]){ 41 if (to)return 0; 42 to=edge[k].to; 43 } 44 v[i+1].push_back(to); 45 pos[to]=j; 46 } 47 } 48 int sum=2*(m-(n-v[1].size()))/(n/v[1].size()); 49 for(int i=0;i<v[1].size();i++){ 50 ve[i].clear(); 51 for(int j=head[v[1][i]];j!=-1;j=edge[j].nex) 52 if (pos[edge[j].to]!=i){ 53 sum--; 54 ve[i].push_back(pos[edge[j].to]); 55 } 56 } 57 if (sum)return 0; 58 for(int i=0;i<v[1].size();i++)sort(ve[i].begin(),ve[i].end()); 59 for(int i=1;i<=n;i++) 60 for(int j=head[i];j!=-1;j=edge[j].nex) 61 if (pos[edge[j].to]!=pos[i]){ 62 int k=lower_bound(ve[pos[i]].begin(),ve[pos[i]].end(),pos[edge[j].to])-ve[pos[i]].begin(); 63 if ((k==ve[pos[i]].size())||(ve[pos[i]][k]!=pos[edge[j].to]))return 0; 64 } 65 return 1; 66 } 67 int main(){ 68 scanf("%d%d",&n,&m); 69 memset(head,-1,sizeof(head)); 70 for(int i=1;i<=m;i++){ 71 scanf("%d%d",&x,&y); 72 add(x,y); 73 add(y,x); 74 r[x]++,r[y]++; 75 } 76 r[0]=r[1]; 77 for(int i=1;i<=n;i++)r[0]=min(r[0],r[i]); 78 for(int i=1;i<=n;i++) 79 if (r[i]==r[0])x=i; 80 bfs(x); 81 memcpy(d0,d,sizeof(d)); 82 for(int i=head[x];i!=-1;i=edge[i].nex){ 83 y=edge[i].to; 84 bfs(y); 85 v[1].clear(); 86 for(int j=1;j<=n;j++) 87 if (d0[j]<d[j])v[1].push_back(j); 88 if ((check())&&(n/v[1].size()>ans)){ 89 ans=n/v[1].size(); 90 for(int j=1;j<=ans;j++)ansv[j]=v[j]; 91 } 92 } 93 if (!ans){ 94 printf("1 %d\n",n); 95 for(int i=1;i<=n;i++)printf("%d ",i); 96 return 0; 97 } 98 printf("%d %d\n",ans,n/ans); 99 for(int i=1;i<=ans;i++){ 100 for(int j=0;j<ansv[i].size();j++)printf("%d ",ansv[i][j]); 101 printf("\n"); 102 } 103 }
[gym102798F]Skeleton Dynamization
原文：https://www.cnblogs.com/PYWBKTDA/p/14359011.html
