问题描述
For a connected undirected weighted graph G, MST (minimum spanning tree) is a subgraph of G that contains all of G's vertices, is a tree, and sum of its edges is minimum possible.
You are given a graph G. If you run a MST algorithm on graph it would give you only one MST and it causes other edges to become jealous. You are given some queries, each query contains a set of edges of graph G, and you should determine whether there is a MST containing all these edges or not.
输入格式
The first line contains two integers n, m (2 ≤ n, m ≤ 5·105, n - 1 ≤ m) — the number of vertices and edges in the graph and the number of queries.
The i-th of the next m lines contains three integers u**i, v**i, w**i (u**i ≠ v**i, 1 ≤ w**i ≤ 5·105) — the endpoints and weight of the i-th edge. There can be more than one edges between two vertices. It's guaranteed that the given graph is connected.
The next line contains a single integer q (1 ≤ q ≤ 5·105) — the number of queries.
q lines follow, the i-th of them contains the i-th query. It starts with an integer k**i (1 ≤ k**i ≤ n - 1) — the size of edges subset and continues with k**i distinct space-separated integers from 1 to m — the indices of the edges. It is guaranteed that the sum of k**i for 1 ≤ i ≤ q does not exceed 5·105.
输出格式
For each query you should print "YES" (without quotes) if there's a MST containing these edges and "NO" (of course without quotes again) otherwise.
样例输入
5 7
1 2 2
1 3 2
2 3 1
2 4 1
3 4 1
3 5 2
4 5 2
4
2 3 4
3 3 4 5
2 1 7
2 1 2
样例输出
YES
NO
YES
NO
解析
考虑克鲁斯卡尔求最小生成树的过程，对于一系列边权相同的边，如果某一条边加入之前该边的两端点就已经在同一个连通块中，这条边就不能加入。同样的道理，如果询问中的边权相同的边也出现了同样的情况，就说明这些边不能同时出现在一棵最小生成树中。
由于Kruskal加边的顺序是固定的，我们可以在跑最小生成树时就在加入一些边权相同的边之前记下当前每个端点所属的连通块。对于询问的边按照权值排序，对每一段同权值的边复原加边之前的并查集(只用复原这些边的端点的fa)后重新模拟一次加边过程，看看是否会出现矛盾。最后要还原为初始并查集(fa[i]=i)。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 500002
#define rg register
using namespace std;
struct edge{
int u,v,w,fu,fv,id;
}e[N];
struct query{
int x,y,w;
query(int _x,int _y,int _w){x=_x;y=_y;w=_w;}
};
vector<query> v;
int n,m,q,i,fa[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int cmp1(const edge &x,const edge &y)
{
return x.w<y.w;
}
int cmp2(const edge &x,const edge &y)
{
return x.id<y.id;
}
int cmp3(const query &a,const query &b)
{
return a.w<b.w;
}
int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void Kruscal()
{
for(rg int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1,cmp1);
for(rg int i=1;i<=m;){
int j=i;
do{
e[j].fu=find(e[j].u);
e[j].fv=find(e[j].v);
j++;
}while(j<=m&&e[j].w==e[j-1].w);
while(i<j){
while(find(e[i].u)==find(e[i].v)&&i<j) i++;
if(i<j) fa[find(e[i].u)]=find(e[i].v);
}
}
}
signed main()
{
n=read();m=read();
for(rg int i=1;i<=m;i++){
e[i].u=read();e[i].v=read();e[i].w=read();
e[i].id=i;
}
Kruscal();
for(rg int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1,cmp2);
q=read();
while(q--){
int x,y,flag=1;
x=read();
v.clear();
for(rg int i=1;i<=x;i++){
y=read();
v.push_back(query(e[y].fu,e[y].fv,e[y].w));
}
sort(v.begin(),v.end(),cmp3);
for(rg int i=0;i<x&&flag;){
if(v[i].x==v[i].y){
flag=0;
break;
}
fa[find(v[i].x)]=find(v[i].y);
int j=i+1;
while(j<x&&v[j].w==v[i].w){
if(find(v[j].x)==find(v[j].y)){
flag=0;
break;
}
fa[find(v[j].x)]=find(v[j].y);
j++;
}
while(i<j){
fa[v[i].x]=v[i].x;fa[v[i].y]=v[i].y;
i++;
}
}
puts(flag ? "YES" : "NO");
}
return 0;
}