团体程序设计天梯赛-练习集 L2-025 分而治之 (25分) vis数组做法与并查集思路

水深无声 2023-10-11 15:06 19阅读 0赞

### L2-025 分而治之 (25分) ###

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

**输入格式：**  
输入在第一行给出两个正整数 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

--------------------

**题目解析：**  首先建立二维数组存储每个节点所关联的边。对于每一种输入的方案，设置方案里面的节点不可访问（这里设置vis数组的节点值为1），遍历二维数组，判断当前未被攻占的城市，是否仍和其他城市有关联，如果有，那么这个方案不可行，否则可行。

--------------------

**并查集思想：** 首先建立连通关系，对于每次输入的方案，也是采用以设置 vis 数组为不可访问，最终对于原来输入的边建立的连通性，可访问的节点上在重新建立连通关系，最后比较连通集合的个数与城市个数是否相等即可。  
相关思路可以借鉴：[L2-013 红色警报 (25分) 题目解析 并查集做法][L2-013 _ _25_ _]  
但是本题不太适用，因为每次都需要以结构体的方式设置两端的城市的编号，以供重新建立。然后比对，那么在此处，建立并查集就比较多余，因为直接可以遍历二维数组，就无需再次重新建立连通关系。

--------------------

代码如下：

#include<bits/stdc++.h>
    #define Inf 0x3f3f3f
    const int N = 10005;
    using namespace std;
    
    int n, m, k;
    int sum;
    vector<int> ve[N];
    int vis[N], flag;
    
    void solve(){
        
    	for(int i = 1; i <= n; i ++)
    		for(int j = 0; j < ve[i].size(); j ++)
    			if(vis[i]==0 && vis[ve[i][j]]==0){
        //当前未被攻占的城市，仍和其他城市有关联
    				flag = 1; return;
    			}
    }
    
    int main(){
        
    	int x, y;
    	cin >> n >> m;
    	while(m--){
        
    		cin >> x >> y;
    		ve[x].push_back(y);
    		ve[y].push_back(x);
    	}
    	
    	int np, ans;
    	cin >> k;
    	while(k--){
        
    		cin >> np;
    		memset(vis, 0, sizeof(vis));
    		while(np--){
        
    			cin >> ans;
    			vis[ans]=1;//设置该节点不能访问
    		}
    		flag = 0;
    		solve();
    		if(flag == 1){
        
    			cout << "NO" << endl;
    		}else{
        
    			cout << "YES" << endl;
    		}
    	}
    	return 0;
    }

[L2-013 _ _25_ _]: https://blog.csdn.net/weixin_43819566/article/details/110120992