[PAT解题报告] Battle Over Cities
给定一个无向图，问删掉一个节点（和与之相关联的边）之后，我们需要再新建多少条边，能保证这个图的其他点互相可达。
分析：我们把一个图切成若干个连通分量——每个连通分量当作一个“大”的节点，这些“大”节点之间是没有边相连的，这些“大”节点内部的真正节点是互相连通的。如果有n个“大”节点，我们连(n
- 1)条边，就可以形成一棵树，所有的真正节点之间也都有道路相连了。
所以这个题本质就是删一个节点之后，看连通分量的个数，减1就是答案。求连通分量可以用bfs和dfs，dfs简单点。另外还要注意，如果原始图只有一个节点，删掉这个节点之后就是一个空的图了——所以算连通分量个数要小心答案是0，答案减成-1的情况。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
bool a[1024][1024];
int visited[1024];
int n;
void dfs(int now,int x) {
if (visited[now]) {
return;
}
visited[now] = true;
for (int i = 0; i < n; ++i) {
if ((x != i) && a[now][i]) {
dfs(i , x);
}
}
}
int main() {
int m,q;
for (scanf("%d%d%d",&n,&m,&q); m; --m) {
int x,y;
scanf("%d%d",&x,&y);
--x;
--y;
a[x][y] = a[y][x] = true;
}
for (;q;--q) {
int x;
scanf("%d",&x);
--x;
memset(visited,0,sizeof(visited));
int answer = 0;
for (int i = 0; i < n; ++i) {
if ((x != i) && (!visited[i])) {
++answer;
dfs(i, x);
}
}
printf("%d\n",max(--answer, 0));
}
return 0;
}
原题链接 http://www.patest.cn/contests/pat-a-practise/1013
华为工作强度 660人发布