用c++书写这个程序：分而治之各个击破是兵家常用的策略之一。在战争中我们希望首先攻下敌方的部分城市使其剩余的城市变成孤立无援然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序判断每个方案的可行性。输入格式：输入在第一行给出两个正整数 N 和 M均不超过10 000分别为敌方城市个数于是默认城市从 1 到 N 编号和连接两城市的通路条数。随后 M 行每行给出一条通路所连接的两个城市

#include #include #include using namespace std;

// 用于表示图的邻接表 vector<vector> graph; // 标记每个城市是否被攻下 vector conquered;

// 使用BFS遍历图，判断方案的可行性 bool isFeasible(int Np, vector cities) { // 重置标记数组 for (int i = 0; i < conquered.size(); i++) { conquered[i] = false; } // 攻下计划攻下的城市 for (int i = 1; i <= Np; i++) { conquered[cities[i]] = true; } // 使用BFS遍历图 queue q; q.push(cities[1]); while (!q.empty()) { int city = q.front(); q.pop(); for (int i = 0; i < graph[city].size(); i++) { int nextCity = graph[city][i]; if (!conquered[nextCity]) { conquered[nextCity] = true; q.push(nextCity); } } } // 检查是否所有城市都被攻下 for (int i = 1; i < conquered.size(); i++) { if (!conquered[i]) { return false; } } return true; }

int main() { int N, M; cin >> N >> M; // 初始化图和标记数组 graph.resize(N+1); conquered.resize(N+1); // 读入通路信息，构建图 for (int i = 0; i < M; i++) { int city1, city2; cin >> city1 >> city2; graph[city1].push_back(city2); graph[city2].push_back(city1); } int K; cin >> K; // 逐个判断方案的可行性 for (int i = 0; i < K; i++) { int Np; cin >> Np; vector cities(Np+1); // 读入计划攻下的城市 for (int j = 1; j <= Np; j++) { cin >> cities[j]; } // 判断方案的可行性并输出结果 if (isFeasible(Np, cities)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0;