PQ thụ

PQ thụ là một loại căn cứ vào thụ số liệu kết cấu, đại biểu một tổ nguyên tố thượng một loạt sắp hàng, từ Kellogg S. Booth cùng George S. Lueker với 1976 năm phát hiện mệnh danh, dùng để giải quyết dưới vấn đề

Cấp raCái tập hợp,Ngươi muốn tìm được một cáiSắp hàng, khiến cho mỗi cái tập hợp nội nguyên tố đều liền nhau.

PQ thụ có thể ởThời gian nội xây dựng. Bổn văn trung giới thiệu xây dựng phương pháp thời gian phức tạp độ vì.

Định nghĩa

PQ thụ có ba loại giao điểm:Lá cây giao điểm,P giao điểmCùngQ giao điểm.Trong đó lá cây giao điểm đại biểu sắp hàng trung một cái nguyên tố, P giao điểm tỏ vẻ nó tử giao điểm có thể tùy ý sắp hàng, Q giao điểm tỏ vẻ nó nhi tử trình tự có thể xoay ngược lại. Sở hữu phi lá cây giao điểm đều là P giao điểm hoặc Q giao điểm trung một loại. P giao điểm ít nhất có 2 đứa con trai, Q giao điểm ít nhất có 3 đứa con trai.
Bởi vì giao điểm định nghĩa, PQ thụ bản thân đại biểuSở hữuHợp pháp phương án, này trước tự biến lịch chính là một trong số đó.
Hạ đồ là một cây PQ thụ.

Này trước tự biến lịch 1,2,3,4,5 đại biểu một cái hợp pháp phương án. Nếu P giao điểm nhi tử trọng sắp hàng vì 4,2,3, chúng ta được đến một cái khác hợp pháp phương án 1,4,2,3,5. Bảo trì P giao điểm nhi tử trình tự bất biến, Q giao điểm nhi tử trình tự xoay ngược lại, được đến một cái khác hợp pháp phương án 5,3,2,4,1.

Xây dựng

PQ thụ sử dụng nhi tử - huynh đệ tỏ vẻ pháp.

Chúng ta tăng lượng xây dựng một cây PQ thụ.

Đầu tiên thành lập một thân cây, này căn vì P, tổng cộngĐứa con trai, phân biệt là,Đại biểu không có bất luận cái gì hạn chế khi PQ thụ. Theo hạn chế không ngừng gia nhập, chúng ta không ngừng sửa chữa này cây.

Đương gia nhập một cái tân hạn chế tập hợpKhi, chúng ta đem sở hữu thuộc về cái này tập hợp lá cây giao điểm đánh dấu vìMàu đen,Không ở cái này tập hợp nội lá cây giao điểm đánh dấu vìMàu trắng.Đối với sở hữu phi lá cây giao điểm, nếu này sở hữu nhi tử đều vì màu đen, đem này cũng đánh dấu vì màu đen; nếu này sở hữu nhi tử đều vì màu trắng, đem này cũng đánh dấu vì màu trắng; nếu không đem này đánh dấu vìMàu xám.Ở dưới đồ trung, màu đen giao điểm, màu trắng giao điểm, màu xám giao điểm phân biệt dùng màu đen, màu xám, một nửa hắc một nửa hôi tới tỏ vẻ.

Chúng ta yêu cầu PQ thụ trung giao điểm dựa theo nhan sắc bài tự.

Tự đế hướng về phía trước pháp

Bao hàm sở hữu màu đen giao điểm nhỏ nhất tử thụ được xưng làTương quan tử thụ,Tương quan tử thụ căn ( không nhất định là chỉnh cây căn ) được xưng làTương quan căn.

Tăng thêm một cái hạn chế quá trình được xưng là reduction. Một lần reduction chia làm hai cái giai đoạn: Mạo phao giai đoạn cùng giảm bớt giai đoạn.

Mạo phao giai đoạn

Mạo phao giai đoạn chỉ xử lý tương quan tử thụ. Chúng ta đem tương quan tử thụ trung sở hữu giao điểm đánh dấu vì màu đen hoặc màu xám, cũng vì mỗi cái giao điểm tính toán này có được tương quan tử giao điểm số lượng. Vì hiệu suất cao mà hoàn thành cái này quá trình, chúng ta từ lá cây hướng căn xử lý tương quan tử thụ. Này yêu cầu ký lục mỗi cái điểm phụ thân giao điểm, nhưng ở giảm bớt giai đoạn một cái điểm phụ thân giao điểm thường xuyên phải bị sửa chữa. Vì tại tuyến tính thời gian nội cấu tạo, chỉ có P giao điểm nhi tử cùngQ giao điểm cuối cùng một cái nhi tửTrước sau ký lục chính xác phụ thân giao điểm. Đối với Q giao điểm mặt khác nhi tử, ở mạo phao giai đoạn dùng cuối cùng một cái nhi tử phụ thân đổi mới bọn họ phụ thân.

Đương gặp được một cái trung gian giao điểm khi, chúng ta xem một chút nó huynh đệ hay không đã có hợp pháp phụ thân giao điểm. Nếu không có, đem này đánh dấu vìTắc.Nếu mặt sau nó huynh đệ có hợp pháp phụ thân, như vậy sửa chữa cái này giao điểm phụ thân hơn nữa hủy bỏ đánh dấu. Nếu ở mạo phao giai đoạn kết thúc khi, vẫn cứ có một đoạn liên tục tắc giao điểm ( như sau mặt tình huống Q3 ), một cái không có phụ giao điểm “Ngụy giao điểm” trở thành nên khối phụ giao điểm, cũng ở giảm bớt giai đoạn khi bị đi trừ.

Giảm bớt giai đoạn

Giảm bớt giai đoạn dùng một cái đội ngũ tới xử lý giao điểm. Đầu tiên đem sở hữu hạn chế nội lá cây giao điểm gia nhập đội ngũ. Mỗi lần lấy ra đội đầu giao điểmCũng xử lý. NếuPhụ thân cũng là tương quan tử thụ nội giao điểm, như vậy đemNhập đội.
Đối với mỗi một cái giao điểm,Chúng ta phân tình huống thảo luận. Nếu không thuộc về trong đó bất luận cái gì một loại tình huống, tắc vô giải.

Lá cây giao điểm

ĐemĐánh dấu vì màu đen.

P giao điểm

Nếu sở hữu nhi tử đều vì màu đen, đemĐánh dấu vì màu đen.

NếuCó màu đen nhi tử cùng màu trắng nhi tử, thảLà tương quan căn, như vậy tân kiến một cái P giao điểmTrở thành nó sở hữu màu đen nhi tử căn.

NếuCó màu đen nhi tử cùng màu trắng nhi tử, thảKhông phải tương quan căn, làm như vậy dưới thao tác:

• Tân kiến một cái P giao điểmTrở thành sở hữu màu đen nhi tử căn.
• Tân kiến một cái P giao điểmTrở thành sở hữu màu trắng nhi tử căn.
• Nếu( cùng / hoặc) chỉ có một cái nhi tử, như vậy không cần tân kiến giao điểm, mà là đem( cùng / hoặc) trực tiếp phú giá trị thành cái kia nhi tử.
• ĐemĐổi thành Q giao điểm cũng đem này nhi tử thiết vìCùng,Đem này đánh dấu vì màu xám.

Chú ý tới căn cứ phía trước định nghĩa, Q giao điểm ít nhất có 3 đứa con trai, bởi vậy nơi nàyBị coi là một cái “Ngụy giao điểm”, hơn nữa đem ở phía sau bị tiếp tục xử lý.

NếuCó một cái màu xám nhi tử,ThảLà tương quan căn, như vậy tân kiến một cái P giao điểmLàm này sở hữu màu đen nhi tử căn, đemHuynh đệ thiết vìCuối cùng từng bước từng bước màu đen nhi tử, sau đó đemThiết vìCuối cùng một cái nhi tử.

NếuCó một cái màu xám nhi tử,ThảKhông phải tương quan căn, như vậy tiến hành dưới thao tác:

• Tân kiến một cái P giao điểmTrở thành sở hữu màu đen nhi tử căn.
• Tân kiến một cái P giao điểmTrở thành sở hữu màu trắng nhi tử căn.
• Nếu( cùng / hoặc) chỉ có một cái nhi tử, như vậy không cần tân kiến giao điểm, mà là đem( cùng / hoặc) trực tiếp phú giá trị thành cái kia nhi tử.
• ĐemHuynh đệ thiết vìCuối cùng một cái màu trắng nhi tử, sau đó đemThiết vìCuối cùng một cái nhi tử.
• ĐemHuynh đệ thiết vìCuối cùng một cái màu đen nhi tử, sau đó đemThiết vìCuối cùng một cái nhi tử.

NếuĐúng lúc có hai cái màu xám nhi tử,Như vậy tiến hành dưới thao tác:

• Tân kiến một cái P giao điểmTrở thành sở hữu màu đen nhi tử căn.
• NếuChỉ có một cái nhi tử, như vậy không cần tân kiến giao điểm, mà là đemTrực tiếp phú giá trị thành cái kia nhi tử.
• ĐemCuối cùng một cái màu đen nhi tử huynh đệ thiết vì.
• ĐemHuynh đệ thiết vìCuối cùng một cái màu đen nhi tử.
• ĐemCuối cùng một cái nhi tử thiết vìCuối cùng một cái màu trắng nhi tử.

Có thể phát hiện như vậyĐã bị xác nhập vào.

Q giao điểm

NếuChỉ có màu đen nhi tử, như vậy đemĐánh dấu thành màu đen. ( phía dưới đồ hình dạng sai rồi. )

NếuCó một cái màu xám nhi tử,Thả sở hữu đánh dấu tương đồng nhi tử đều liên tục xuất hiện, như vậy tiến hành như sau thao tác:

• ThiếtVìCuối cùng một cái màu đen nhi tử,VìCuối cùng một cái màu trắng nhi tử,VìMàu đen huynh đệ,VìMàu trắng huynh đệ.
• ĐemHuynh đệ thiết vì,Huynh đệ thiết vì.
• NếuKhông có một cái màu trắng huynh đệ hoặc màu đen huynh đệ, đemCuối cùng một cái nhi tử thiết thànhCuối cùng một cái nhi tử.
• Xóa bỏ.

NếuĐúng lúc có hai cái màu xám nhi tử,Thả sở hữu đánh dấu tương đồng nhi tử đều liên tục xuất hiện, như vậy đốiĐều tiến hành thượng một loại thao tác là được.

Nên xây dựng phương pháp là nguyên luận văn trung, nhưng là thực hiện tương đối không tiện.

Tự đỉnh xuống phía dưới pháp

Trước mắt OI trung thực hiện phần lớn chọn dùng nên phương pháp. Kỳ thật phương pháp cùng loại, phía dưới xuất hiện tình huống cơ bản đều có thể ở mặt trên tìm được.

Chú ý tới căn cứ phía trước nhuộm màu quá trình, sở hữu màu đen cùng màu trắng điểm đều đã thỏa mãn điều kiện, bởi vậy chúng taChỉ cần xử lý màu xám giao điểm.

P giao điểm

• NếuCó bao nhiêu với hai cái màu xám nhi tử, vô giải.
• NếuChỉ có một cái màu xám nhi tử, thả không có màu đen nhi tử, đệ quy xử lý màu xám nhi tử.
• Nếu không trước quét sạchNhi tử, sau đó gia nhập sở hữu màu trắng nhi tử. Tân kiến một cái Q giao điểmCũng trở thànhNhi tử. ỞTrung gia nhập sở hữu màu xám nhi tử. Tân kiến một cái P giao điểmLàm sở hữu màu đen nhi tử căn, đemCắm vàoTrung gian. ( đối ứng tự đế hướng về phía trước pháp P giao điểm sở hữu tình huống. )

Chú ý tới chúng ta sẽ yêu cầu hai cái màu xám tiết điểm màu trắng tất cả tại bên trái, màu đen tất cả tại phía bên phải ( hoặc tương phản ), bởi vậy chúng ta yêu cầu thực hiện một cái phân liệt hàm sốsplit,Có thể đem cái này tử thụ điểm phân liệt thành hắc bạch bộ phận, cũng đồng thời giữ lại phân liệt thành tử thụ tiết điểmSở hữu khả năng.

Q giao điểm

• Tìm được nhất bên trái cùng nhất bên phải phi màu trắng tiết điểm vị trí.NếuNội có phi màu đen tiết điểm, vô giải.
• Nếu không có màu đen tiết điểm, chỉ có một cái màu xám tiết điểm, đệ quy xử lý cái này màu xám tiết điểm, nếu không chỉ cần đemCùngVị trí tiết điểm phân liệt.

Phân liệt hàm số

Lệnh muốn phân liệt điểm vì,Chúng ta tưởng đemPhân liệt thành bên trái tất cả đều là màu trắng, bên phải tất cả đều là màu đen rừng rậm. NếuKhông phải màu xám giao điểm tắc trực tiếp phản hồi tử thụ. Chỉ suy xét màu xám giao điểm tình huống. NếuLà P loại giao điểm:

• NếuCó ít nhất hai cái màu xám nhi tử, tắc vô giải.
• Nếu không bên trái là sở hữu màu trắng nhi tử, trung gian đệ quy xử lý màu xám nhi tử, bên phải là sở hữu màu đen nhi tử. Chú ý tới muốn giữ lại sở hữu khả năng, bởi vậy muốn tân kiến hai cái P giao điểm phân biệt làm màu trắng nhi tử cùng màu đen nhi tử căn. ( đối ứng tự đế hướng về phía trước pháp P4 tình huống. )
• Xóa bỏ.

NếuLà Q loại giao điểm:

• Nếu chính tự cùng phản tự đều không thỏa mãn bạch - hôi - hắc, tắc vô giải.
• Nếu có ít nhất hai cái màu xám nhi tử, cũng không giải.
• Nếu không đệ quy phân liệt màu xám nhi tử là được.
• Xóa bỏ.

Cuối cùng đem sở hữu dư thừa giao điểm ( chỉ có một cái nhi tử giao điểm ) xóa bỏ.

Số hiệu thực hiện

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

classPQTree{
public:
PQTree(){}

voidInit(intn){
n_=n,rt_=tot_=n+1;
for(inti=1;in;i++)g_[rt_].emplace_back(i);
}

voidInsert(conststd::string&s){
s_=s;
Dfs0(rt_);
Work(rt_);
while(g_[rt_].size()==1)rt_=g_[rt_][0];
Remove(rt_);
}

std::vectorint>ans(){
DfsAns(rt_);
returnans_;
}

~PQTree(){}

private:
intn_,rt_,tot_,pool_[100001],top_,typ_[100001]/* 0-P 1-Q */,
col_[100001]/* 0-black 1-white 2-grey */;
std::vectorint>g_[100001],ans_;
std::strings_;

voidFail(){
std::cout"NO\n";
std::exit(0);
}

intNewNode(intty){
intx=top_?pool_[top_--]:++tot_;
typ_[x]=ty;
returnx;
}

voidDelete(intu){g_[u].clear(),pool_[++top_]=u;}

voidDfs0(intu){// get color of each node
if(u>=1&&un_){
col_[u]=s_[u]=='1';
return;
}
boolc0=false,c1=false;
for(auto&&v:g_[u]){
Dfs0(v);
if(col_[v])c1=true;
if(col_[v]!=1)c0=true;
}
if(c0&&!c1)
col_[u]=0;
elseif(!c0&&c1)
col_[u]=1;
else
col_[u]=2;
}

boolCheck(conststd::vectorint>&v){
intp2=-1;
for(inti=0;istatic_castint>(v.size());i++)
if(col_[v[i]]==2){
if(p2!=-1)returnfalse;
p2=i;
}
if(p2==-1)
for(inti=0;istatic_castint>(v.size());i++)
if(col_[v[i]]){
p2=i;
break;
}
for(inti=0;ip2;i++)
if(col_[v[i]])returnfalse;
for(inti=p2+1;istatic_castint>(v.size());i++)
if(col_[v[i]]!=1)returnfalse;
returntrue;
}

std::vectorint>Split(intu){
if(col_[u]!=2)return{u};
std::vectorint>ng;
if(typ_[u]){// Q
if(!Check(g_[u])){
std::reverse(g_[u].begin(),g_[u].end());
if(!Check(g_[u]))Fail();
}
for(auto&&v:g_[u])
if(col_[v]!=2){
ng.emplace_back(v);
}else{
autos=Split(v);
ng.insert(ng.end(),s.begin(),s.end());
}
}else{// P
std::vectorint>son[3];
for(auto&&x:g_[u])son[col_[x]].emplace_back(x);
if(son[2].size()>1)Fail();
if(!son[0].empty()){
intn0=NewNode(0);
g_[n0]=son[0];
ng.emplace_back(n0);
}
if(!son[2].empty()){
autos=Split(son[2][0]);
ng.insert(ng.end(),s.begin(),s.end());
}
if(!son[1].empty()){
intn1=NewNode(0);
g_[n1]=son[1];
ng.emplace_back(n1);
}
}
Delete(u);
returnng;
}

voidWork(intu){
if(col_[u]!=2)return;
if(typ_[u]){// Q
intl=1e9,r=-1e9;
for(inti=0;istatic_castint>(g_[u].size());i++)
if(col_[g_[u][i]])checkmin(l,i),checkmax(r,i);
for(inti=l+1;ir;i++)
if(col_[g_[u][i]]!=1)Fail();
if(l==r&&col_[g_[u][l]]==2){
Work(g_[u][l]);
return;
}
std::vectorint>ng;
for(inti=0;il;i++)ng.emplace_back(g_[u][i]);
autos=Split(g_[u][l]);
ng.insert(ng.end(),s.begin(),s.end());
for(inti=l+1;ir;i++)ng.emplace_back(g_[u][i]);
if(l!=r){
s=Split(g_[u][r]);
std::reverse(s.begin(),s.end());
ng.insert(ng.end(),s.begin(),s.end());
}
for(inti=r+1;istatic_castint>(g_[u].size());i++)
ng.emplace_back(g_[u][i]);
g_[u]=ng;
}else{// P
std::vectorint>son[3];
for(auto&&x:g_[u])son[col_[x]].emplace_back(x);
if(son[1].empty()&&son[2].size()==1){
Work(son[2][0]);
return;
}
g_[u].clear();
if(son[2].size()>2)Fail();
g_[u]=son[0];
intn1=NewNode(1);
g_[u].emplace_back(n1);
if(son[2].size()>=1){
autos=Split(son[2][0]);
g_[n1].insert(g_[n1].end(),s.begin(),s.end());
}
if(son[1].size()){
intn2=NewNode(0);
g_[n1].emplace_back(n2);
g_[n2]=son[1];
}
if(son[2].size()>=2){
autos=Split(son[2][1]);
std::reverse(s.begin(),s.end());
g_[n1].insert(g_[n1].end(),s.begin(),s.end());
}
}
}

voidRemove(intu){// remove the nodes with only one child
for(auto&&v:g_[u]){
inttv=v;
while(g_[tv].size()==1){
intt=tv;
tv=g_[tv][0];
Delete(t);
}
v=tv,Remove(v);
}
}

voidDfsAns(intu){
if(u>=1&&un_){
ans_.emplace_back(u);
return;
}
for(auto&&v:g_[u])DfsAns(v);
}
}T;

Bài tập

• CF243E Matrix
• CF1552I Organizing a Music Festival

Tham khảo tư liệu

• Booth, Kellogg S. & Lueker, George S. (1976)."Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms".Journal of Computer and System Sciences.13(3): 335–379.doi:10.1016/S0022-0000(76)80045-1.
• PQ Tree Algorithm and Consecutive Ones Problem
• CF243E Matrix PQTree - RainAir's Blog

Bổn giao diện gần nhất đổi mới:2023/5/6 19:22:00,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:isdanni,xyf007,CCXXXI,Ir1d,ksyx,R-G-Mocoratioen,Tiphereth-A
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng