分析性质题（集合类）：CF1371F

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

感觉浪费了一道好题，没有好好分析性质

---

若非叶子节点有连边，则存在两个集合的交集为 { x , y } \{x,y\} {x,y}

然后就可以区分叶子和非叶子节点

对于叶子节点，包含它大小最小的集合就是对应的集合。

---

对于非叶只计算<=1距离的点，设为 $G$

显然在非叶>=3时 $G$ 互不相同。

对于叶子节点集合取掉叶子节点结合后唯一对应的 $G$ 就是自己的父亲

发现上述过程可以bitset优化

#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 1010
//#define M
//#define mo
int n, m, i, j, k, T;
vector<pair<int, int> >ans; 
map<pair<int, int>, int>mp; 
//bitset<10>S, G[N], t, s[N]; 
bitset<N>S, G[N], t, s[N]; 
int p[N], c[N], mn, x, y; 
int f[N]; 

void sol1() {
	for(i=2; i<=n; ++i) printf("1 %d\n", i); 
}

void sol2() {
	S=t=0; 
	for(i=1; i<=n; ++i) {
		if(!p[i]) continue; 
		k=f[i]; 
		if(S.count()==0 || s[k]==S) ans.pb({x, i}), S=s[k]; 
		else ans.pb({y, i}), t=s[k]; 
	}
	for(auto t : ans) printf("%d %d\n", t.first, t.second); 

}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); mn=1e9; 
	if(n==2) return printf("1 2\n"), 0; 
	for(i=1; i<=n; ++i) {
		p[i]=1; 
		c[i]=read(); mn=min(mn, c[i]); 
		for(j=1; j<=c[i]; ++j) {
			k=read(); s[i][k]=1; 
		}
//		cout<
	}
	if(mn==n) return sol1(), 0; 
	for(i=1, k=0; i<=n; ++i)
		for(j=i+1; j<=n; ++j) {
			S=(s[i]&s[j]); 
			if(S.count()!=2) continue; 
			x=S._Find_first(); y=S._Find_next(x); 
			p[x]=p[y]=0; // they are not leaf
			if(!mp[{x, y}]) ans.pb({x, y}), ++k; 
			mp[{x, y}]=1;  
			G[x][y]=G[y][x]=G[x][x]=G[y][y]=1; 
		}
//	for(i=1; i<=n; ++i) 
//		for(j=1; j<=n; ++j) 
//			if(i!=j && (s[i]|s[j])==s[j]) ans.pb({i, j}); 
//	for(i=1; i<=n; ++i) cout<
	S=0; //叶子节点的集合 
	for(i=1; i<=n; ++i) if(p[i]) S[i]=1; 
//	printf("S : \n"); cout<
	for(i=1; i<=n; ++i) if(p[i]) {
		mn=1e9; 
		for(j=1; j<=n; ++j) 
			if(s[j][i] && s[j].count()<mn) f[i]=j, mn=s[j].count(); 
		
	}
	if(k==1) return sol2(), 0; 
	for(i=1; i<=n; ++i) if(p[i]) {
		k=f[i]; t=(S&s[k]); 
			t=(s[k]^t); 
//			printf(">> %d : %d ", i, k); cout<
			for(j=1; j<=n; ++j) if(G[j]==t) ans.pb({j, i}); 
	}
	for(auto t : ans) printf("%d %d\n", t.first, t.second); 
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92