题目大意:输入一个 m 条边的无向图,有 q 个询问,每次询问一组边集,问是否存在一个MST包含这组边。
基于Kruscal算法的一个结论:若有一棵MST包含这条边(u,v),那么所有权值比这条边小的边组成的森林或无向图,(u,v)仍不连通。换句话说,权值比这条边小的边都考虑了之后,再考虑(u,v)这条边,(u,v)仍然不会成环。
考虑离线的做法
:将边按
权值
分块,将询问边按
边权为第一关键字
,
所属问题编号
为第二关键字分块,从小到大枚举权值。当枚举到权值 w 时,将权值在 [1,w – 1]的边都用上。枚举边权为w且属于同一组询问的询问边,用并查集将连通块连起来,判断过程中是否会形成环,若形成环则说明一定不存在一棵MST同时包含这些边。
由于有多组询问,对下一组做判断时,前一组的判断要做撤销操作,因此需要撤销并查集。
撤销并查集其实就是不用路径压缩来优化,使用
按秩合并(启发式合并)
来优化使得一次查找的复杂度大约在
log
n
\log n
lo
g
n
,这样可以支持撤销操作,只需要记录合并前的根节点以及深度。
撤销操作必须按合并操作的逆序来执行,即需要一个栈来维护已经合并的操作,按逆序恢复到原来的状态。
例如:第一次合并是蓝色的树,第二次合并是红色的树,此时深度为3
,
要撤销两次合并操作,如果先撤销红色,再撤销蓝色,最后深度是1,反之如果先撤销蓝色,再撤销红色,深度是2,因为深度记录的是上一次合并的状态。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
#define pii pair<int,int>
#define fir first
#define sec second
pair<pii,int> edg[maxn];
int n,m,q;
int p[maxn],dep[maxn],ans[maxn];
vector<pii> qry[maxn];
vector<int> tot[maxn];
int find(int x) {
return x == p[x] ? x : find(p[x]);
}
void merge(int x,int y) {
int fx = find(x),fy = find(y);
if(fx == fy) return;
if(dep[fx] > dep[fy]) swap(fx,fy);
if(dep[fx] + 1 > dep[fy]) dep[fy]++;
p[fx] = fy;
}
void solve(int w,int l,int r) {
vector<pair<int,pii>> sta;
for(int i = l; i <= r; i++) {
int x = qry[w][i].sec;
int fx = find(edg[x].fir.fir),fy = find(edg[x].fir.sec);
if(fx == fy) {
ans[qry[w][i].fir] = 1;
} else {
if(dep[fx] > dep[fy]) swap(fx,fy);
sta.push_back(make_pair(fx,pii(fy,dep[fy])));
if(dep[fx] + 1 > dep[fy]) dep[fy] = dep[fx] + 1;
p[fx] = fy;
}
}
reverse(sta.begin(),sta.end());
for(auto it : sta) {
//撤销这些操作,用栈的原因是深度变化必须倒过来,否则顺序错乱会错
p[it.fir] = it.fir;
dep[it.sec.fir] = it.sec.sec;
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
p[i] = i;
for(int i = 1,u,v,w; i <= m; i++) {
scanf("%d%d%d",&u,&v,&w);
edg[i] = make_pair(pii(u,v),w);
tot[w].push_back(i);
}
scanf("%d",&q);
for(int i = 1; i <= q; i++) {
int k;scanf("%d",&k);
for(int j = 1,x; j <= k; j++) {
scanf("%d",&x);
qry[edg[x].sec].push_back(pii(i,x));
}
}
for(int i = 1; i <= maxn - 10; i++) { //枚举权值
for(int l = 0,r; l < qry[i].size(); l = r + 1) {
r = l;
while(r + 1 < qry[i].size() && qry[i][r + 1].fir == qry[i][r].fir) r++;
solve(i,l,r);
}
for(auto it : tot[i]) {
int u = edg[it].fir.fir;
int v = edg[it].fir.sec;
merge(u,v);
}
}
for(int i = 1; i <= q; i++) {
if(ans[i] == 1) puts("NO");
else puts("YES");
}
return 0;
}