题目描述
Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of $ n $ cities connected by the $ n-1 $ road, such that you can get from each city to any other one along the roads. However, the information about the specific design of roads in Treeland has been lost. The only thing that the archaeologists can use is the preserved information about near cities.
Two cities of Treeland were called near, if it were possible to move from one city to the other one by moving through at most two roads. Also, a city is considered near to itself. During the recent excavations archaeologists found a set of $ n $ notes, each of them represents a list of cities, near to some of the $ n $ cities of the country. However, unfortunately, none of the found records lets you understand in what order the cities go in the list and for which city in the list the near to it cities were listed.
Help the archaeologists and restore any variant of the map of Treeland that meets the found information.
输入格式
The first line contains integer $ n $ ( $ 2<=n<=1000 $ ) — the number of cities in the country.
Next $ n $ lines describe the found lists of near cities. Each list starts from number $ k $ ( $ 1<=k<=n $ ), representing the number of cities in the list followed by $ k $ city numbers. All numbers in each list are distinct.
It is guaranteed that the given information determines at least one possible road map.
输出格式
Print $ n-1 $ pairs of numbers representing the roads of the country. The $ i $ -th line must contain two integers $ a_{i},b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ), showing that there is a road between cities $ a_{i} $ and $ b_{i} $ .
The answer you print must satisfy the description of close cities from the input. You may print the roads of the countries in any order. The cities that are connected by a road may also be printed in any order.
If there are multiple good answers, you may print any of them.
样例 #1
样例输入 #1
5
4 3 2 4 1
5 5 3 2 4 1
5 4 2 1 5 3
4 2 1 4 3
3 1 4 5
样例输出 #1
1 4
1 2
1 3
4 5
样例 #2
样例输入 #2
6
5 6 1 3 4 2
5 2 1 3 4 6
6 3 6 2 5 4 1
6 6 1 2 5 3 4
3 5 2 4
5 3 1 2 4 6
样例输出 #2
2 4
1 2
2 3
2 6
4 5
首先，任何一条连接两个非叶子节点的边，他们一定是某两个集合的交集。
然后用 bitset 暴力就可以得到所有非叶子节点之间的连边。
考虑叶子节点要连到那个点上，首先叶子节点对应的集合一定是包含他的所有集合中大小最小的那个。
叶子节点距离不超过2的店中一定有一个点和其他所有点有连边，用 bitset 找到这个点。
但是要是和一个叶子距离不超过2的只有三个点？那说明有一个点在排除叶子节点的树中是个叶子，找到并和叶子节点相连。
特判菊花图和只有两个非叶子节点的情况。前者直接输出，后者用并查集判断每个叶子节点属于那边。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,k,s[2],in[N],mn[N],wh[N],fa[N],p[N],m;
vector<int>g[N];
bitset<N>w[N],mp[N],nw;
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int main()
{
memset(mn,0x7f,sizeof(mn));
scanf("%d",&n);
if(n==2)
{
puts("1 2");
return 0;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
g[i].resize(k);
for(int j=0;j<k;j++)
{
scanf("%d",&g[i][j]);
if(k<mn[g[i][j]])
mn[g[i][j]]=k,wh[g[i][j]]=i;
w[i][g[i][j]]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
bitset<N>t=w[i]&w[j];
if(t.count()==2)
{
for(int j=t._Find_first(),c=0;j<N;j=t._Find_next(j),++c)
s[c]=j;
mp[s[0]][s[1]]=mp[s[1]][s[0]]=1;
in[s[0]]++,in[s[1]]++;
}
}
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(mp[i][j])
++m,printf("%d %d\n",i,j);
if(m==1)
{
for(int i=1;i<=n;i++)
if(!in[i])
fa[i]=i;
for(int i=1;i<=n;i++)
{
if(in[i])
continue;
for(int j:g[wh[i]])
if(!in[j])
fa[find(j)]=find(i);
}
for(int i=1,c=0;i<=n;i++)
if(!in[i]&&fa[i]==i)
p[i]=s[c++];
for(int i=1;i<=n;i++)
if(!in[i])
printf("%d %d\n",i,p[find(i)]);
}
else if(m)
{
// for(int i=1;i<=m;i++)
// printf("%d %d\n",e[i].first,e[i].second);
for(int i=1;i<=n;i++)
{
if(in[i])
continue;
int p=0,c=0;
for(int j:g[wh[i]])
{
if(!in[j])
continue;
if(c<2)
s[c]=j;
++c;
nw=mp[j]&w[wh[i]];
if(nw.count()==1)
p=nw._Find_first();
}
if(c^2)
printf("%d %d\n",i,p);
else
printf("%d %d\n",i,in[s[0]]<in[s[1]]? s[0]:s[1]);
}
}
else
{
for(int i=2;i<=n;i++)
printf("1 %d\n",i);
}
}