本题思路，考虑到真正删除给出的城市节点很麻烦，我们可以考虑在dfs时，如果访问到该节点就返回，这样就避免选中与该节点相连接的节点，本题可以转化为求最大连通子图的个数问题。
#include<cstdio> #include<iostream> #include<vector> #include<cstring> using namespace std; const int maxn=1010; vector<int> G[maxn]; bool vis[maxn]={false}; int now; void DFS(int x) { if(x==now) return ; vis[x]=true; for(int i=0;i<G[x].size();i++) { if(vis[G[x][i]]==false) DFS(G[x][i]); } } int main() { int n,m,k,a,b; cin>>n>>m>>k; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } for(int i=0;i<k;i++) { scanf("%d",&now); memset(vis,false,n+1); int num=0; for(int j=1;j<=n;j++) { if(j!=now&&vis[j]==false) { DFS(j); num++; } } printf("%d\n",num-1); } }