PAT-L2-025 分而治之 (25分)-图论-邻接链表

news/2024/7/15 18:03:49 标签: 图论

分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。

输入格式:
输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (≤ 100)和随后的 K 行方案,每行按以下格式给出:

Np v[1] v[2] … v[Np]

其中 Np 是该方案中计划攻下的城市数量,后面的系列 v[i] 是计划攻下的城市编号。

输出格式:
对每一套方案,如果可行就输出YES,否则输出NO。

输入样例:
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

输出样例:
NO
YES
YES
NO
NO

本题其实也是常规题,我们用一个标记数组来表示被攻打过的城市,然后依次遍历所有的城市,如果这个城市被攻打过,就不用判断,如果没有被攻打过,那就判断他是否是孤立的,如果他周围的点都被攻打过,那么他就是孤立的,所以,只要有一个城市不符合条件,就直接退出,输出NO,否则为YES

//@author:hairu,wu
//@from:ahut
#include<iostream>
#include<vector>
#include<memory.h>
using namespace std;
const int max_n=1e5;

int n,m;
vector<int> edges[max_n];
bool visited[max_n];

bool check(){
	//n为所有城池的编号,从1开始
	bool flag=true;
	for(int i=1;i<=n;i++){
		if(visited[i]) continue;//这个点被攻打过了,那么就不用去判断其临近的点了,因为这个点已经被孤立了 
		for(int j=0;j<edges[i].size();j++){
			int next=edges[i][j];
			if(!visited[next]){
				flag=false;
				break;
			}
		}
		if(flag==false) break;
	} 
	return flag;
}

int main(){
	cin >> n>> m;
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x>>y;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	int k;
	cin >> k;
	for(int i=0;i<k;i++){
		memset(visited,false,sizeof(visited));
		int num;
		cin >> num;
		for(int j=0;j<num;j++){
			int x;
			cin >> x;
			visited[x]=true;//表示被攻打下来 
		}
		if(check()){
			//如果可以全部被独立出来 
			cout<<"YES"<<endl; 
		}else{
			cout<<"NO"<<endl;
		}
	}
	
	return 0;
}

在这里插入图片描述


http://www.niftyadmin.cn/n/1438080.html

相关文章

PAT-L2-026 小字辈 (25分)

本题给定一个庞大家族的家谱&#xff0c;要请你给出最小一辈的名单。 输入格式&#xff1a; 输入在第一行给出家族人口总数 N&#xff08;不超过 100 000 的正整数&#xff09; —— 简单起见&#xff0c;我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号&#xff0c;其…

牛客网-玛雅人的密码-BFS

题目描述 玛雅人有一种密码&#xff0c;如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串&#xff0c;&#xff08;2<N<13&#xff09;该字符串中只含有0,1,2三种数字&#xff0c;问这个字符串要移位几次才能解开密码&#xff0c;每次只能移动相邻…

大数的阶乘-手动模拟法

题目&#xff1a;给定一个n,求得n!.比如&#xff1a;3&#xff0c;输出6 可以利用大数的原理&#xff0c;进行手动乘法&#xff0c;模拟即可 ///author:hairu,wu //from:ahut #include<iostream> #include<memory.h> using namespace std;struct bign{int a[2000…

牛客网-今年的第几天-日期的处理

题目描述 输入年、月、日&#xff0c;计算该天是本年的第几天。 输入描述: 包括三个整数年(1<Y<3000)、月(1<M<12)、日(1<D<31)。 输出描述: 输入可能有多组测试数据&#xff0c;对于每一组测试数据&#xff0c; 输出一个整数&#xff0c;代表Input中的年、月…

最大子矩阵(DP)

本题其实可以抽象成一个动态规划的题目&#xff0c;我们要求的这个子矩阵不是正方形的&#xff0c;其实我们可以将矩阵进行压缩&#xff0c;想象成一维的&#xff0c;这样&#xff0c;我们在求解的时候&#xff0c;实际上就是求解最大连续子序列和&#xff0c;所以&#xff0c;…

合唱队形-(DP)-最长单增子序列和最长单减子序列变形

题目描述 N位同学站成一排&#xff0c;音乐老师要请其中的(N-K)位同学出列&#xff0c;使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形&#xff1a;设K位同学从左到右依次编号为1, 2, …, K&#xff0c;他们的身高分别为T1, T2, …, TK&#xff0c…

解决jQuery无法提交表单的问题

今天在修改项目的时候&#xff0c;用jQuery通过submit方法来提交表单&#xff0c;发现提交不了&#xff0c;结果差了很多资料&#xff0c;才知道&#xff1a; 也就是我的form表单里的一个Input标签的id设置为了submit 。。。。修改为其他的即可完美提交。。。坑啊、。

Windows底下安装Anoconda,搭建tensorflow和openCV环境详细过程

以最短的语言简述Windows底下安装Anoconda&#xff0c;搭建tensorflow和openCV环境详细的过程&#xff1a; 安装Anoconda 下载网址&#xff1a;https://www.anaconda.com/products/individual 选择自己电脑系统&#xff0c;然后下载对应的版本&#xff0c;下载完成后&#xff…