PAT A1013 Battle Over Cities (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<vector> 
using namespace std;
/* 题意： 给定一个无向图，当删除一个结点时会同时删除与之连接的边，进行k次查询 求每次删除该结点后需要增加多少边，才能使图变为连通图 思路：需要增加的边数=删除结点后的连通分量数-1，因此问题转化为求删除结点后的连通分量，而 要求连通分量可以进行图的遍历（因为图的遍历时都是逐个访问单个连通块）， 最后还有一个问题就是如何删除这个结点，其实不必真正删去，而是当遍历访问到这个点的时候直接return即可 注意： 1、由于n<1000,故图的存储即可采用邻接矩阵又可采用邻接表 （但一般都使用邻接表，毕竟当n很大的时候就不好用邻接矩阵存储图） 2、对于图的遍历，则可以采用DFS，或者BFS 3、对于图的题目还是尽量用scanf来读入数据，否则容易超时。 实在只想用cin,cout,则记得ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)即可 */

//步骤一：图遍历的相关定义，邻接表，vis数组 
const int N=1e3+10; 
vector<int> g[N];//邻接表 
bool vis[N];//vis[i]==true表示点i已经被访问 
int n,m,k,delPoint; 
//步骤三：dfs遍历图 
void dfs(int v){
	//递归边界 
	if(v==delPoint)return;//如果访问到删除的点就直接return
	vis[v]=true;
	for(int i=0;i<g[v].size();i++){
		if(!vis[g[v][i]]){//如果点g[v][i]未被访问，则继续dfs 
			dfs(g[v][i]);
		}
	}
} 
int main(){
    //提高cin的读入效率
	ios::sync_with_stdio(false); 
	cin.tie(0);
	cin>>n>>m>>k;
	//步骤二：对图进行存储 
	for(int i=0,a,b;i<m;i++){
		//由于是无向图，注意相互之间都要存边 
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i=0;i<k;i++){
		cin>>delPoint;
		fill(vis,vis+N,false);//注意题意说明每次都是在原图的基础上删除结点
		int block=0;//连通分量数
		//步骤四遍历每个连通块 
		for(int i=1;i<=n;i++){
			if(!vis[i]&&i!=delPoint){//若该结点未被删除且未被访问 
				dfs(i);
				block++;
			} 
		} 
		printf("%d\n",block-1); 
	} 
	
	return 0;
}