当前位置:网站首页>[exercise-6] (PTA) divide and conquer
[exercise-6] (PTA) divide and conquer
2022-07-06 15:56:00 【Flame car】
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”;
边栏推荐
- Interesting drink
- Perinatal Software Industry Research Report - market status analysis and development prospect forecast
- China's PCB connector market trend report, technological innovation and market forecast
- 渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
- 信息安全-安全编排自动化与响应 (SOAR) 技术解析
- China exterior wall cladding (EWC) market trend report, technical dynamic innovation and market forecast
- Opencv learning log 19 skin grinding
- SSM框架常用配置文件
- Accounting regulations and professional ethics [4]
- CEP used by Flink
猜你喜欢
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
Record of force deduction and question brushing
Nodejs+vue online fresh flower shop sales information system express+mysql
Learning record: understand systick system timer and write delay function
Matlab example: two expressions of step function
程序员的你,有哪些炫技的代码写法?
渗透测试 ( 4 ) --- Meterpreter 命令详解
Information security - threat detection engine - common rule engine base performance comparison
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
Borg Maze (BFS+最小生成树)(解题报告)
随机推荐
Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
Opencv learning log 19 skin grinding
0-1背包问题(一)
China earth moving machinery market trend report, technical dynamic innovation and market forecast
E. Breaking the Wall
0-1 knapsack problem (I)
Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
Flink 使用之 CEP
China potato slicer market trend report, technical dynamic innovation and market forecast
Research Report on market supply and demand and strategy of China's medical chair industry
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Ball Dropping
入门C语言基础问答
China's peripheral catheter market trend report, technological innovation and market forecast
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
Learning record: USART serial communication
Gartner:关于零信任网络访问最佳实践的五个建议
Market trend report, technical innovation and market forecast of Chinese hospital respiratory humidification equipment
STM32如何使用STLINK下载程序:点亮LED跑马灯(库版本)
Matlab example: two expressions of step function