Restoring Map
星空蚁来了秒了。
人与人的智力是有差距的。
刷再多的CF智力不行就是不行。
OI这种需要智力的游戏不适合我。
我还是更适合对智力要求低一点的。
比如和妹子贴贴。
但是也没有妹子。
life is hard.
这类树的构造似乎可以从边缘情况想起,比如 CF1844G
但是这个题从叶节点(称为2类点)开始想就寄了。
我们把点 x 的集合称为 \(S_x\)
考虑观察非叶节点(称为1类点)是否直接连边的性质,称直接相连的两点为 x,y。
那么我们可以找出一条形如 a-x-y-b 的链,则 \(S_a\cup S_b=\left\{x,y\right\}\)
不难证明该条件充要。
对于1类点个数 \(\geq\) 3个的,我们可以把所有1类点找出来,这些点首先需要连边。
再考虑所有2类点,其能连到的1类点为其父亲和爷爷,找出集合包含当前2类点的那个即可(如果都有就随便,这说明两者父子关系不定)
对于只有1个1类点,构造一个菊花图即可。
对于2个1类点,这时所有2类点分成两部分,相同集合的必须连同一个点,这个也很好判断。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define mp make_pair
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define b1t bitset
typedef pair<int,int> kk;
void read(int &x){
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
const int MAXN=1005;
int n;
b1t<MAXN> a[MAXN],b[MAXN],ye;
bool pd,vis[MAXN];
vector<kk> res;
int main(){
read(n);
pd=1;
for(int i=1,op,x;i<=n;i++){
read(op);
pd&=(op==n);
while(op--)
{read(x);
a[i][x]=1;
}
}
if(pd){
for(int i=2;i<=n;i++) printf("%d %d\n",1,i);
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b1t<MAXN> tmp=a[i]&a[j];
if(tmp.count()==2){
int x=tmp._Find_first(),y=tmp._Find_next(x);
if(b[x][y]) continue;
b[x].set(y);b[y].set(x);ye[x]=ye[y]=1;
b[x][x]=b[y][y]=1;res.push_back(mp(x,y));
}
}
}
if(ye.count()==2){
int o1=0,o2=0;
for(int i=1;i<=n;i++){
if(ye[i]){
if(!o1) o1=i;
else{
o2=i;break;
}
}
}
for(int i=1;i<=n;i++){
if(a[i].count()<n){
for(int j=1;j<=n;j++){
if(!ye[j]&&a[i][j]) vis[j]=1;
}
break;
}
}
for(int i=1;i<=n;i++) if(!ye[i]){
if(vis[i]) res.push_back(mp(o1,i));
else res.push_back(mp(o2,i));
}
for(auto u:res) printf("%d %d\n",u.first,u.second);
return 0;
}
for(int i=1;i<=n;i++){
pd=1;
for(int j=1;j<=n;j++){
if((a[i]&a[j])==a[j]&&a[i]!=a[j]){pd=0;break;}
}
if(!pd) continue;
b1t<MAXN> tmp=a[i]&ye;
for(int j=1;j<=n;j++){
if(tmp[j]&&b[j]==tmp){
if(!vis[j]){
for(int k=1;k<=n;k++){
if(!ye[k]&&a[i][k]) res.push_back(mp(j,k));
}
vis[j]=1;
}
break;
}
}
}
for(auto u:res) printf("%d %d\n",u.first,u.second);
return 0;
}