Untitled diff
创建于 差异永不过期
#include <cstdio>
#include<bits/stdc++.h>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#define maxn 600009
using namespace std;
using namespace std;
int UU[maxn], VV[maxn], WW[maxn], q[maxn];
const int maxn= 600100;
using namespace std;
int a[maxn], b[maxn], c[maxn], q[maxn];
typedef struct
typedef struct
{
{
int l,r;
int l,r;
}node;
}node1;
node seg[maxn];
node1 seg[maxn];
typedef struct
typedef struct
{
{
int u,v,w,id;
int u,v,w,id;
}node1;
}node2;
node1 edge[maxn];
node2 edge[maxn];
bool cmp(node1 x,node1 y)
bool cmp(node2 x,node2 y)
{
{
return x.w<y.w;
return x.w<y.w;
}
}
int p[maxn];
int p[maxn];
int findset(int x)
int findset(int x)
{
{
return x==p[x]?x:p[x]=findset(p[x]);
return x==p[x]?x:p[x]=findset(p[x]);
}
}
void unionset(int x,int y)
void unionset(int x,int y)
{
{
p[findset(x)]=findset(y);
p[findset(x)]=findset(y);
}
}
int vis[maxn];
int vis[maxn];
bool wa[maxn];
bool wa[maxn];
set<int>st;
set<int>st;
struct Edge
struct Edge
{
{
int to,id;
int to,id;
};
};
vector<Edge>G[maxn];
vector<Edge>G[maxn];
int type[maxn];
int type[maxn];
map<int, int>mp;
map<int, int>mp;
vector< vector<int> > V[maxn];
vector< vector<int> > V[maxn];
vector<int>tmp[maxn], cr;
vector<int>tmp[maxn], cr;
vector<int>buf;
vector<int>buf;
bool NO[maxn];
bool NO[maxn];
int fdset(int x){
int fdset(int x){
return q[x] == x ? x : q[x] = fdset(q[x]);
return q[x] == x ? x : q[x] = fdset(q[x]);
}
}
void unset(int x, int y){
void unset(int x, int y){
q[fdset(x)] = fdset(y);
q[fdset(x)] = fdset(y);
}
}
void doit(vector <int> &G){
void doit(vector <int> &G){
cr.clear();
cr.clear();
int lb = G[0];
int lb = G[0];
for(int j = 1; j < (int)G.size(); j++){
for(int j = 1; j < (int)G.size(); j++){
int u = UU[G[j]];
int u = a[G[j]], v = b[G[j]];
int v = VV[G[j]];
u = findset(u);v = findset(v);
u = findset(u);
v = findset(v);
if(fdset(u) == fdset(v)){
if(fdset(u) == fdset(v)){
NO[lb] = 1;
NO[lb] = 1;
}
}
unset(u, v);
unset(u, v);
cr.push_back(u);
cr.push_back(u);cr.push_back(v);
cr.push_back(v);
if(NO[lb])break;
if(NO[lb])
break;
}
}
for(auto x: cr)
for(auto x: cr)q[x] = x;
q[x] = x;
}
}
void check(int x){
void check(int x){
for(int i = 0; i < (int)V[x].size(); i++){
for(int i = 0; i < (int)V[x].size(); i++){
doit(V[x][i]);
doit(V[x][i]);
}
}
}
}
int main()
int main()
{
{
int n,m;
int n,m;
scanf("%d%d",&n,&m);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int i=1;i<=n;i++){
p[i]=i;
p[i]=i;q[i] = i;
q[i] = i;
}
}
for(int i=0;i<m;i++)
for(int i=0;i<m;i++)
{
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
UU[i + 1] = edge[i].u;
a[i+1] = edge[i].u;
VV[i + 1] = edge[i].v;
b[i+1] = edge[i].v;
WW[i + 1] = edge[i].w;
c[i+1] = edge[i].w;
edge[i].id=i+1;
edge[i].id=i+1;
}
}
sort(edge,edge+m,cmp);
sort(edge,edge+m,cmp);
int cur=0,tot=0;
int cur=0,tot=0;
while(cur<m)
while(cur<m)
{
{
seg[tot].l=cur;
seg[tot].l=cur;
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
while(cur+1<m&&edge[cur].w==edge[cur+1].w)
cur++;
cur++;
seg[tot].r=cur;
seg[tot].r=cur;
mp[edge[cur].w] = tot;
mp[edge[cur].w] = tot;
cur++;tot++;
cur++;tot++;
}
}
int Q;
int q;
scanf("%d", &Q);
scanf("%d", &q);
for(int i = 1; i <= Q; i++){
for(int i = 1; i <= q; i++){
buf.clear();
buf.clear();buf.push_back(i);
buf.push_back(i);
cr.clear();
cr.clear();
int num;
int num;
scanf("%d", &num);
scanf("%d", &num);
for(int j = 0; j < num; j++){
for(int j = 0; j < num; j++){
int x;
int x;
scanf("%d", &x);
scanf("%d", &x);
int w = mp[WW[x]];
int w = mp[c[x]];
if((int)tmp[w].size() == 0){
if((int)tmp[w].size() == 0){
tmp[w].push_back(i);
tmp[w].push_back(i);
tmp[w].push_back(x);
tmp[w].push_back(x);
cr.push_back(w);
cr.push_back(w);
}
}
else{
else{
tmp[w].push_back(x);
tmp[w].push_back(x);
}
}
buf.push_back(x);
buf.push_back(x);
}
}
for(auto x: cr){
for(auto x: cr){
V[x].push_back(tmp[x]);
V[x].push_back(tmp[x]);
tmp[x].clear();
tmp[x].clear();
}
}
doit(buf);
doit(buf);
}
}
//cout << tot << endl;
for(int i=0;i<tot;i++)
for(int i=0;i<tot;i++)
{
{
check(i);
check(i);
for(int j = seg[i].l; j <= seg[i].r; j++){
for(int j = seg[i].l; j <= seg[i].r; j++){
unionset(edge[j].u, edge[j].v);
unionset(edge[j].u, edge[j].v);
}
}
}
}
for(int i = 1; i <= Q; i++)
for(int i = 1; i <= q; i++)
if(NO[i])
{
if(NO[i]){
puts("NO");
puts("NO");
else
}
else{
puts("YES");
puts("YES");
}
}
return 0;
return 0;
}
}