Problem surface

analysis

First, according to Kruskal algorithm,

We can know,

When an edge with a weight of \ (w \) is added,

All edges with weights less than \ (w \) have been added to the tree (except for the linked ones).

Therefore, we can save the connected block of each edge's endpoint before joining the spanning tree.

Sort the sides of the inquiry by the edge weight.

For each group of edges with the same weight end,

It is restored to the connectivity of the edge with this weight.

It's enough to judge whether a ring can be formed.

(there may be a lot of details to pay attention to)

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;

inline int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}

const int N=500001;
struct edge{int fx,fy,x,y,w,id;}e[N<<1];
int n,m,Q;
int fa[N];
vector <int> s;

bool cmp(edge a,edge b){return a.w<b.w;}
bool cmp2(edge a,edge b){return a.id<b.id;}
bool cmp3(int a,int b){return e[a].w<e[b].w;}

inline int find_fa(int x){return x==fa[x]? x:fa[x]=find_fa(fa[x]);}

int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].w=read();
    for(int i=1;i<=m;i++) e[i].id=i;
    for(int i=1;i<=n;i++) fa[i]=i;
    sort(e+1,e+m+1,cmp);e[0].w=-1;
    for(int i=1;i<=m;){
        int j=i;
        do{e[j].fx=find_fa(e[j].x);e[j].fy=find_fa(e[j].y);j++;}while(e[i].w==e[j].w&&j<=m);
        while(i<j){
            while(find_fa(e[i].x)==find_fa(e[i].y)&&i<j) i++;
            if(i<j) fa[find_fa(e[i].x)]=find_fa(e[i].y);
        }
    }
    sort(e+1,e+m+1,cmp2);
    Q=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    while(Q--){
        int ok=1,ss=read();
        for(int i=1;i<=ss;i++){int x=read();s.push_back(x);}
        sort(s.begin(),s.end(),cmp3);
        int sz=s.size();
        for(int i=0;i<sz&&ok;){
            if(e[s[i]].fx==e[s[i]].fy){ok=0;break;}
            fa[find_fa(e[s[i]].fx)]=find_fa(e[s[i]].fy);
            int j=i+1;
            while(j<sz&&e[s[i]].w==e[s[j]].w){
                if(find_fa(e[s[j]].fx)==find_fa(e[s[j]].fy)){ok=0;break;}
                fa[find_fa(e[s[j]].fx)]=find_fa(e[s[j]].fy);j++;
            }
            while(i<j) fa[e[s[i]].fx]=e[s[i]].fx,fa[e[s[i]].fy]=e[s[i]].fy,i++;         
        }
        puts(ok? "YES":"NO");s.clear();
    }
    return 0;
}