邊集是否會出現在最小生成樹中 Codeforce 891 C(可撤銷並查集)
題目連結：
https：//
codeforces。com/contest/
891/problem/C
題意：
給定一個
個點，
條邊的圖。每條邊都有權值
。
給出
組詢問。
每次給出
條邊，詢問是否存在一個最小生成樹，使得這
條邊都在最小生成樹中。
思路：
我們可以回想下每次只詢問一條邊的是怎麼做的。
我們可以模擬克魯斯卡爾生成樹的過程，按照邊權從小到大開始跑最小生成樹。
當我們已經處理完
![[1,w - 1]](https://img.heatask.com/upload/website_attach/8Fg8qAAIF-EyqHZ0G=kt8t_08Dn5FNoUM7s8onE3XF+Rrsm5keLn1ZbuGT254WTtx+zp7NE3mFpj7xenpIk3p=9sJeWuk.jpeg)
所有的邊，如果邊
的
已經處於一個聯通快裡面，那麼顯然，這條邊不會出現在任何一個最小生成樹中。
那麼對於詢問一組邊集，我們可以先儲存所有的詢問。然後從小到大維護最小生成樹。
已經將
處理完後，我們開始處理邊權為
且
位於同一組詢問的邊
。
看看這些邊會不產生環，如果產生環，那麼整個詢問就都不行了。
問題是，每次我們在處理一組詢問的邊後，還需要處理相同邊權下的其他詢問的邊，所以這個時候就需要可撤銷並查集了。
我們處理完一組詢問的邊後，撤銷剛才新增的邊。
前置知識嚴格鴿：ACM——可撤銷並查集教程
這樣我們就可以跑出這個題目了。
我們用
map
<
int
，
vector
<
int
>>
g
［
MAXN
］；
來儲存每種邊權下，處於相同的詢問的邊的編號。
code
struct
edge
{
int
u
，
v
，
w
；
}
e
［
MAXN
］；
map
<
int
，
vector
<
int
>>
g
［
MAXN
］；
vector
<
int
>
mp
［
MAXN
］；
int
ans
［
MAXN
］；
void
slove
（）
{
cin
>>
n
>>
m
；
dsu
。
init
（
n
）；
for
（
int
i
=
1
；
i
<=
m
；
i
++
）
{
int
u
，
v
，
w
；
cin
>>
u
>>
v
>>
w
；
e
［
i
］
=
{
u
，
v
，
w
}；
mp
［
w
］。
push_back
（
i
）；
}
cin
>>
q
；
for
（
int
i
=
1
；
i
<=
q
；
i
++
）
{
ans
［
i
］
=
1
；
int
k
；
cin
>>
k
；
while
（
k
——
）
{
int
ed
；
cin
>>
ed
；
g
［
e
［
ed
］。
w
］［
i
］。
push_back
（
ed
）；
}
}
for
（
int
w
=
1
；
w
<=
5e5
；
w
++
）
{
for
（
auto
p
：
g
［
w
］）
{
int
h
=
dsu
。
histroy
（）；
for
（
int
i
：
p
。
second
）
{
if
（
dsu
。
same
（
e
［
i
］。
u
，
e
［
i
］。
v
））
ans
［
p
。
first
］
=
0
；
dsu
。
merge
（
e
［
i
］。
u
，
e
［
i
］。
v
）；
}
dsu
。
roll
（
h
）；
}
for
（
int
i
：
mp
［
w
］）
dsu
。
merge
（
e
［
i
］。
u
，
e
［
i
］。
v
）；
}
for
（
int
i
=
1
；
i
<=
q
；
i
++
）
{
if
（
ans
［
i
］）
YES
；
else
NO
；
}
}
