CF566E-Restoring Map【bitset】

On the subject

Topic link :https://www.luogu.com.cn/problem/CF566E

---

The main idea of the topic

There is a tree. , But you don't know its shape . Now you only know that the distance from each point is no more than $2$ Point set of , But you don't know which point each point set corresponds to .

Now I want you to beg the tree .

$2\le n\le 1000$

---

Their thinking

Consider a situation like this

that $?$ and ${?}^{\prime }$ The intersection of is exactly $x$ and $y$, That is, we can determine all the edges of non leaves in the above way .

Then consider how to determine the edge of the leaf , For leaves $x$ Come on , The smallest of the sets containing it must be its own set .

So we can determine the set corresponding to each leaf , Then consider how to ask its father .

We will find that if we remove the leaves from the set of leaves , That leaves only its parent node and other non leaf nodes connected to its parent node .

We then deal with a set of non leaf nodes with edges , Then one by one, we can find the father of this point .

Then we have to judge some special situations ：

1. No non leaf nodes ： here $n=2$ Direct special judgment .
2. There is only one non leaf node ： At this point, any point can be used as a non leaf node .
3. There are only two non leaf nodes ： At this point, the set of leaves can be divided into two cases , Just correspond to different parent nodes .

use $bitset$ Optimization can achieve $O(\frac{n^3}{\omega })$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<vector>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1050;
int n,k[N],f[N];;
bitset<N> b[N],g[N],c,v;
vector<pair<int,int> >e;
int main()
{
    
	scanf("%d",&n);
	for(int i=0;i<n;i++)f[i]=n,g[i][i]=1;k[n]=n+1;
	if(n==2)return puts("1 2")&0;
	for(int i=0;i<n;i++){
    
		scanf("%d",&k[i]);
		for(int j=1,x;j<=k[i];j++){
    
			scanf("%d",&x);x--;b[i][x]=1;
			f[x]=(k[i]<k[f[x]])?i:f[x];
		}
	}
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++){
    
			c=b[i]&b[j];
			if(c.count()==2){
    
				int a=c._Find_first();
				int b=c._Find_next(a);
				e.push_back(mp(min(a,b),max(a,b)));
				g[a][b]=g[b][a]=v[a]=v[b]=1;
			}
		}
	if(v.count()==0){
    
		for(int i=1;i<n;i++)
			printf("%d %d\n",i+1,1);
		return 0;
	}
	else if(v.count()==2){
    
		int p=v._Find_first();
		int q=v._Find_next(p);
		printf("%d %d\n",p+1,q+1);
		bool flag=0;
		for(int i=0;i<n;i++)
			if(!v[i]){
    
				if(flag){
    
					if(b[f[i]]==c)
						printf("%d %d\n",i+1,p+1);
					else printf("%d %d\n",i+1,q+1);
				}
				else printf("%d %d\n",i+1,p+1),c=b[f[i]],flag=1;
			}
		return 0;
	}
	for(int i=0;i<n;i++){
    
		if(v[i])continue;b[f[i]]&=v;
		for(int j=0;j<n;j++)
			if(b[f[i]]==g[j]){
    e.push_back(mp(min(i,j),max(i,j)));break;}
	}
	sort(e.begin(),e.end());
	for(int i=0;i<e.size();i++)
		if(!i||e[i]!=e[i-1])printf("%d %d\n",e[i].first+1,e[i].second+1);
	return 0;
}