【计蒜之道2016复赛】【计蒜客A1107】青云的网络设计方案 题解

题目大意

  有一棵树，有 $n$ 个点。现在将所有距离为 $2$ 的点对也连一条边。
  给出最终的图，请构造一棵原来的树。

  多组数据，$T \leq 10,\ \ n \leq10^4,\ \ m \leq 10^5$

$$\\$$ $$\\$$ $$\\$$

题解

  （很强势的题，可能由于那场复赛大家都在肝别的题吧，这题想想还是挺可做的。）

  首先随便扒一个点做根。我们把根叫做第 1 层。

  从第 1 层扩出去的点，就是第 2 层和第 3 层了。我们把这些点叫做第 2/3 层。

  那么从第 2/3 层扩出去的新点，就是第 4/5 层了。并且，如果这个新点只被访问了一次，说明是第 3 层访问了第 5 层，因此这个点是第 5 层；若被访问了 2 次，说明是第 2 层和第 3 层访问了第 4 层，因此这个点是第 4 层。
  也就是说，从 2/3 层往外扩，可以知道第 4 层和第 5 层。

  然后从第 4 层往外扩，新点就是第 6 层；再从第 5 层往外扩，新点就是第 7 层……

  最后的问题就是处理第 2 层和第 3 层。
  首先观察第 2/3 层的连边形成的图形。第 2 层的点之间互相连边，因此是一个团，而各自的第 3 层儿子们也是互相连边，因此形成的结构是：先有一个团，然后团上的某些点再向外连一个小团。
  因此可以得出结论：只考虑第 2/3 层的连边，如果有多种度数，那么度数最大的点一定是第 2 层的（称为情况 1）。但如果所有点度数一样，那么说明是第 2 层只有一个点（称为情况 2）。两种情况分别解决。

  情况 1：我们找到了一个一定在第 2 层的点 $x$，那么它连不到的就是别人家的第 3 层，这些第 3 层连到的就是第 2 层。
  如果我们这样能确定另一个一定在第 2 层的点 $y$，那么剩下的点中，$y$ 能连到的就是第 2 层，连不到的就是 $x$ 的儿子也就是第 3 层，就做完了。
  如果无法确定 $y$，说明 $x$ 的兄弟都没有儿子。那么看是否存在第 4 层，第 4 层能连到的就是 $x$ 的儿子也就是第 3 层，连不到的就是第 2 层。如果不存在第 4 层，那么 $x$ 的兄弟团和儿子团其实是没有本质区别的，选择其中一个团作为儿子团，另一个团作为兄弟团就行了。

  情况2：先看有没有第 5 层，第 5 层连到的都是第 3 层。完了之后，注意到第 2 层的那个点会连向所有第 4 层，而第 3 层的点只会连向部分第 4 层，因此看谁被第 4 层访问得最多，谁就是第 2 层。若有相同，任选皆可。

  现在每个点的层数确定了。最后扫一遍即可。

  UPD：2018icpc Regional Seoul 出了这个原题，但是不保证一定有解，因此还要判各种恶心的 -1 的情况。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=1e6+5;

int n,m,cnt[maxn],dg[maxn],oo;
vector<int> e[maxn];

vector<int> lev[2*maxn];
int deep[maxn];
void ins(int l,int i)
{
	lev[l].push_back(i);
	deep[i]=l;
}

void find1()
{
	for(int go:e[1]) ins(oo,go);
}
void find23()
{
	for(int i:lev[oo])
		for(int go:e[i]) if (!deep[go]) cnt[go]++;
	for(int i:lev[oo])
		for(int go:e[i])
		{
			if (cnt[go]==2) ins(4,go);
			if (cnt[go]==1) ins(5,go);
		}
}
void find(int l)
{
	for(int i:lev[l])
		for(int go:e[i]) if (!deep[go]) ins(l+2,go);
}

int fa[maxn];
void dfs_ans(int k,int last)
{
	fa[k]=last;
	for(int go:e[k]) if (deep[go]==deep[k]+1) dfs_ans(go,k);
}

void init()
{
	fo(i,1,n) e[i].clear(), lev[i].clear(), deep[i]=fa[i]=dg[i]=cnt[i]=0;
	lev[oo].clear();
}

int T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d",&n,&m);
		oo=100003;
		init();
		fo(i,1,m)
		{
			int x,y;
			scanf("%d %d",&x,&y);
			e[x].push_back(y), e[y].push_back(x);
		}
		
		ins(1,1);
		find1();
		find23();
		for(int i=4; lev[i].size()>0; i++) find(i);
		
		int fi=0, se=0;
		for(int i:lev[oo])
		{
			fi=i;
			for(int go:e[i]) if (deep[go]==oo) dg[go]++;
		}
		fo(i,1,n) if (dg[i]>dg[fi]) se=fi, fi=i;
			else if (dg[fi]>dg[i] && dg[i]>dg[se]) se=i;
		if (!se && fi)
		{
			for(int i:lev[5])
				for(int go:e[i]) if (deep[go]==oo) ins(3,go);
			memset(cnt,0,sizeof(cnt));
			for(int i:lev[4])
				for(int go:e[i]) if (deep[go]==oo) cnt[go]++;
			for(int i:lev[oo]) if (deep[i]==oo && cnt[i]>cnt[fi]) fi=i;
			ins(2,fi);
			for(int i:lev[oo]) if (deep[i]==oo) ins(3,i);
		} else if (fi)
		{
			memset(cnt,0,sizeof(cnt));
			cnt[fi]=1;
			ins(2,fi);
			for(int go:e[fi]) if (deep[go]==oo || deep[go]==3) cnt[go]++;
			for(int i:lev[oo]) if (!cnt[i]) ins(3,i);
			for(int i:lev[oo]) if (!cnt[i])
				for(int go:e[i]) if (deep[go]==oo) ins(2,go);
			bool pd=0;
			for(int i:lev[2]) if (i!=fi)
			{
				pd=1;
				for(int go:e[i]) if (deep[go]==oo) ins(2,go);
				for(int i:lev[oo]) if (deep[i]==oo) ins(3,i);
				break;
			}
			if (!pd)
			{
				for(int go:e[fi]) if (deep[go]==4)
					for(int gogo:e[go]) if (deep[gogo]==oo) ins(3,gogo);
				for(int i:lev[3])
					for(int go:e[i]) if (deep[go]==oo) ins(3,go);
				for(int i:lev[oo]) if (deep[i]==oo) { fi=i; break; }
				ins(2,fi);
				for(int go:e[fi]) if (deep[go]==oo) ins(2,go);
				for(int i:lev[oo]) if (deep[i]==oo) ins(3,i);
			}
		}
		
		dfs_ans(1,0);
		fo(i,2,n) printf("%d %d\n",fa[i],i);
	}
}