题目链接:
https://pintia.cn/problem-sets/994805046380707840/problems/994805056195379200
题意描述:
看上去好像是割点,但又没有什么关系。给城市数和路数,和路相连的两城市组。我军的计划总数和计划中攻打的敌国城市编号。判断如果把这些城市打掉之后,是不是所有的城市都没有路去其他城市了,输出。
解题思路:
原本的思路是暴力,不给ac就很烦。其实这题关键在路,而非点。
先建立一个结构体数组,把有路联通的两座城市存起来。
再建一个mapp映射,以那些毁掉的城市的编号作为键,并修改值。
炸完城市之后就从0~m遍历结构体,如果存在路的两座城市都没有被毁,表示计划失败。反之计划成功。
最后记得clear一下mapp,把毁掉的城市都复原了,才能继续循环计划。
ac代码:
#include<stdio.h>
#include<map>
using namespace std;
struct node{
int x,y;
};
int main()
{
int n,m;
scanf("%d%d",&n,&m); // from 1
struct node way[m];
for(int i=0;i<m;i++)
scanf("%d%d",&way[i].x,&way[i].y); //这个结构体里的城市数据都是联通的
map<int,int>mapp;
int k,np,a;
scanf("%d",&k);
while(k--)
{
int flag=0;
scanf("%d",&np);
while(np--) //炸毁城市
{
scanf("%d",&a);
mapp[a]=1; //值为 1,表示城市被炸了
}
map<int,int>::iterator it;
for(int i=0;i<m;i++) //查验
{
if(mapp[way[i].x]==0&&mapp[way[i].y]==0)
{
flag=1;
printf("NO\n");
break;
}
}
if(flag==0)
printf("YES\n");
mapp.clear();
}
return 0;
}