传送门
参考题解
#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; }