团体设计程序天梯赛L2-025 # 分而治之

---

题目解读

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

输入格式

第一行给一个N和M，表示敌方城市个数和连接两城市的通路条数。
随后M行，每行给出一条通路所连接的两个城市的编号，

输出格式

对于每套方案，如果可行就输出YES，否则输出NO。

思路

攻击完之后,遍历每个顶点,判断其是否有边相连，如果有的话则NO

Ac Code

#include<bits/stdc++.h>using namespace std;const int N =1e4+10;struct range{int x,y;
}r[N]; int main(){int n,m; cin >> n >> m;for(int i=0; i<m; i++){cin >> r[i].x >> r[i].y;}int k;cin >> k;while(k--){//记录哪条边被攻击了 map<int,bool> mp;int t;cin >> t;for(int i=0; i<t; i++){int x;cin >> x;mp[x]=1;}//遍历所有边,bool flag=true; for(int i=0; i<m; i++){//一条边被打了就可以 if(mp.count(r[i].x) || mp.count(r[i].y)){continue;}//如果有一条边没有被攻击,势必有不孤立的城市 flag=false;break;} if(flag)cout<<"YES";else cout<<"NO";cout << endl; }return 0;
}

参考

B站up主 : 一天五顿饭

---

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

---