CF1477D Nezzar and Hidden Permutations 题解

题目描述

给出 $m$ 对限制关系 $(l_i,r_i)$ , 要求构造两个排列 $P,Q$ ，使得对于每个限制，$P_{l_i}-P_{r_i}$ 和 $Q_{l_i}-Q_{r_i}$同号，且使得 $P_i=Q_i$ 的数量尽可能小。

解题思路

我们发现，如果在 $l_i$ 和 $r_i$ 之间连一条边 ，那么限制就是要求给每条边定向，使得图是一个 $\text{DAG}$ 并且，$P,Q$ 都是这个图的拓扑序。

首先有一个性质，如果一个点的度数为 $n-1$ ，那么当边的方向确定之后，这个点在拓扑序中的位置就确定了，因为从它连出去的一定在它后边，连到它的一定在它前边。

那么这些点的 $P$ 和 $Q$ 就一定是相同的了。

因此我们先通过迭代，每次找到一个度数为当前点数减一的点，把它删掉。

这个可以用拓扑排序完成。

设删完之后图里有 $n^{\prime }$ 个点，接下来我们证明存在一种构造使得这 $n^{\prime }$ 个点的 $P,Q$ 互不相同。

在现在这个图中，每个点的度数都是小于 $n-1$的，但这好像并没有什么用。

于是我们观察这个图的反图，可以发现每个连通块都至少有2两个点。

然后就是人类智慧的体现了。

考虑反图一个 $n$ 个点的菊花图$(n\ge 2)$，可以发现这样的图是一定存在构造的。

构造如下：首先把这个菊花图的根节点的 $P$ 和 $Q$ 分别设为 $1,n$。

对于其他的点，我们把他们顺序排成一排，他们的 $P$ 依次设为 $2,3,\dots \dots n$,他们的 $Q$ 依次设为 $1,2,\dots \dots n-1$。

对于在原图的边，如果连的两个点都不是根节点，那么显然大小关系是一样的，而因为反图中是菊花，所以原图中没有连向根节点的边，因此就得证了。

由此我们还可以推出，在这个菊花图上再加几条边，依旧是存在构造的，因为在反图加边相当于是在原图删边，那么就是限制变少了，肯定更可以了。

也就是说，如果这个图有一个生成树是菊花就行了。

由此，我们可以想到是否可以找出原图的一棵生成树，然后把这个生成树划分成若干个菊花呢？

答案是可以的。

考虑依次加点，如果新加的这个点连接的所有点中所有点都没有被划分过，那么就可以把这个点和它连接的点划分成一个菊花。

如果有一至少一个点被划分过，我们可以随便找出一个点，设为 $x$。

首先，$x$ 一定不是它所属菊花的根，否则当前点也会被划分到这个菊花。

那么如果这个菊花内有大于2个点，那么就把 $x$ 从原本的菊花中删了，并和当前点构成一个新的菊花。

如果恰好有2个点，那么可以把那个菊花的根变成 $x$ ,并把当前点划分到这个菊花内。

显然这样可以完成划分。

划分完了之后，对于不同的菊花，我们只需要让他们的值域不一样酒席就够了。

这样的话，同一个菊花内的限制显然是合法的，不在同一个菊花的限制因为值域不同，大小关系也是一定的，因此就完成了所有限制了。

还有一个问题是跑出反图的一个生成树，我们可以用 $set$ 维护 没有被加入到树中的点，然后每次遍历 $set$ 把和当前点没边的点删掉并连边。

#include
using namespace std;
const int N = 5e5 + 5;
int n,m;
int deg[N],P[N],Q[N],siz[N],rot[N],col[N],cnt;
vector<int> G[N];
set<int> S,E[N];
queue<int> q;
vector<int> A[N];
inline void Add(int u,int v) {E[u].insert(v);E[v].insert(u);++deg[u];++deg[v];}
inline void add(int u,int v){G[u].push_back(v);G[v].push_back(u);}
void dfs(int u,int pre){for(auto v:S)if(!E[u].count(v))add(u,v);for(auto v:G[u])if(v!=pre)S.erase(v);for(auto v:G[u])if(v!=pre)dfs(v,u);}
void Extend(int u,int pre) 
{
	bool flag=0;
	if(!col[u]) 
	{
		for(auto v:G[u])
		if(!col[v]) flag=1;
		if(flag) 
		{
			col[u]=++cnt;
			rot[col[u]]=u;
			siz[col[u]]=1;
			for(auto v:G[u]) 
			{
				if(!col[v]) 
				{
					++siz[col[u]];
					col[v]=col[u];
				}
			}
		} 
		else 
		{
			for(auto v:G[u])
			if(col[v]) 
			{
				if(rot[col[v]]==v) 
				{
					++siz[col[v]]; 
					col[u]=col[v];
				} 
				else if(siz[col[v]]>2) 
				{
					col[u]=++cnt;
					rot[col[u]]=u; 
					siz[col[u]]=2;
					--siz[col[v]];
					col[v]=col[u];
				} 
				else 
				{
					rot[col[v]]=v;
					col[u]=col[v];
					++siz[col[u]];
				}
				break;
			}
		}
	}
	for(auto v:G[u]) 
	if(v!=pre)
	Extend(v,u);
}
template <typename T>inline void read(T &x)
{
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
void solve()
{
	read(n);read(m);
	int tot=n;
	cnt=0;
	for(int i=1;i<=n;i++) 
	{
		deg[i]=col[i]=siz[i]=P[i]=Q[i]=0;
		E[i].clear(); 
		G[i].clear();
		A[i].clear();
		S.insert(i);
	}
	for(int i=1;i<=m;i++) 
	{
		int u,v; 
		read(u);read(v);
		Add(u,v);
	}
	for(int i=1;i<=n;i++)
	if(deg[i]== n-1) 
	{
		S.erase(i);
		q.push(i);
	}
	while(!q.empty()) 
	{
		int u=q.front(); 
		q.pop();
		P[u]=Q[u]=tot--;
		for(auto v:E[u])
		{
			--deg[v];
			if(S.count(v)&&deg[v]>=tot-1) 
			{
				q.push(v); 
				S.erase(v);
			}
		}
	}
	for(int i=1;i<=n;i++) 
	if(S.count(i)) 
	{ 
		S.erase(i); 
		dfs(i,0); 
	}
	for(int i=1;i<=n;i++) 
	if(!P[i]&&!col[i]) 
	Extend(i,0);
	for(int i=1;i<=n;i++) 
	if(col[i]) A[col[i]].push_back(i);
	int now=1;
	for(int i=1;i<=cnt;i++) 
	{
		Q[rot[i]]=now;
		for(auto u:A[i]) 
		{
			if(u!=rot[i]) 
			{
				P[u]=now;
				Q[u]=++now;
			}
		}
		P[rot[i]]=now++;
	}
	for(int i=1;i<=n;i++)
	printf("%d ",P[i]);
	printf("\n");
	for(int i=1;i<=n;i++)
	printf("%d ",Q[i]);
	printf("\n");
	
}
int main() 
{ 
	int T=1; 
	read(T);
	while(T--) 
	{
		solve();
	} 
	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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156