[exercise-6] (PTA) divide and conquer

subject ：

Divide and rule (25 branch )

Divide and rule , It is one of the common strategies of the strategists to break each other . In the war , We hope to capture some of the enemy's cities first , Leave the rest of the city alone , Then break them separately . To this end, the staff has provided a number of strike programs . Please write a program for this question , Judge the feasibility of each plan .

Input format ：

Enter two positive integers on the first line N and M（ Not more than 10 000）, Number of enemy cities （ So the default city is from 1 To N Number ） And the number of roads connecting the two cities . And then M That's ok , Each line gives the number of the two cities connected by a road , Separated by a space . After the city information, give a series of plans of the staff , It's a positive integer K （≤ 100） And then K Line plan , Each line is given in the following format ：

Np v[1] v[2] … v[Np]
among Np It's the number of cities planned to be conquered in this plan , Later series v[i] It's the number of the planned city .

Output format ：

For each package , Output if possible YES, Otherwise output NO.

sample input ：

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

sample output ：

NO
YES
YES
NO
NO

At first glance, I thought it was a problem of joint search , Again, it seems that it's not the same thing .
This question is output after deleting several positions , Are the remaining points connected to other points , without （ Relatively independent , be isolated and helpless ） It outputs “YES” Otherwise output NO.
for example ：
1 2 be interlinked 2 3 be interlinked , If you remove 2 The only thing left is 1 3 It's a disconnected output “YES", And if you delete 1 Words 2 3 It is still interlinked, inconsistent and helpless , So the output ”NO“

I know that , In fact, it's not very difficult .

CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    
	int x,y;
}a[10005];
int k[10005];
int main() 
{
    
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y;
	int ww;
	cin>>ww;
	for(int i=1;i<=ww;i++)
	{
    
		int q,x;
		cin>>q;
		for(int j=1;j<=q;j++)
		{
    		
			cin>>x;
			k[x] = 1;
		}
		int f = 1;
		for(int j=1;j<=m;j++)
		{
    
			if(k[a[j].x]==0 && k[a[j].y]==0)
			{
    
				cout<<"NO"<<endl;
				f = 0;
				break; 
			}
		}
		if(f)
			cout<<"YES"<<endl; 
	}
	return 0;
}

The code analysis ：

Record each edge （ It should work, too pair）, Two points represent a line .
Then mark a point , If this point is to be deleted, then k[x] = 1. In this case , As long as one of the two points on an edge is deleted , This side doesn't exist , In other words, we just need to judge whether the two points of each side have been deleted （ One or two ） that will do . If there is an edge, two points have not been deleted , Then output “NO”;