PAT 1013 Battle Over Cities——求图的连通分支个数

题解

原题链接
题目翻译过来的意思就是给你一个无向图，删掉其中一个顶点然后让你求剩下的图的连通分支个数
求连通分支个数有以下两种方法：

1. dfs，直到所有节点都被访问过，记录下dfs次数就是连通分支个数，删除顶点放在dfs里面加一个判断就可以了
2. 并查集，但是这题涉及到删除一些边，没有dfs来的方便

ps：这题我一开始使用的cin读入，最后超时了一个，改为scanf才AC

代码（参考算法笔记）

#include 
#include 
#include 
#define maxv 1001using namespace std;void dfs(int v);bool vis[maxv];
int N, M, K,occupy;
vector<int> G[maxv];int main()
{scanf("%d %d %d",&N,&M,&K);for (int i=1; i<=M; i++){int v1, v2;scanf("%d %d",&v1, &v2);G[v1].push_back(v2);G[v2].push_back(v1);}for(int i=1; i<=K; i++){int cnt = 0;scanf("%d",&occupy);for (int j=1; j<=N; j++){if (vis[j]==false && j!=occupy){dfs(j);cnt++;}vis[j] = false;}cout << cnt-1 << endl;}return 0;
}void dfs(int v)
{if (v == occupy)return;vis[v] = true;for (int i=0; i<G[v].size(); i++){if (vis[G[v][i]] == false)dfs(G[v][i]);}
}

end

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！