题目粗心：

给定N座城市,其中有M条边是相连的,如果有其中一个城市被敌人霸占的话,求出须要连贯多少条边让剩下的城市连通.

算法思路:

该城市的数据结构很显然是一个图的构造,那么咱们如果将一个顶点去除后，剩下来的顶点会组成若干个连通重量,那么要让这剩下来的结点全副连接起来变成一个图，那么就等价于将若干个连通重量连接成一个连通重量,咱们晓得2个连通重量只须要在这2个连通重量别离取出一个顶点而后相连就变成了一个连通重量,所以须要连贯的边数就是若干连通重量减一的个数。统计连通重量的个数的形式就是在每次DFS完结后累加就好。应用惯例的DFS代码就能够解决了。

留神点：

  • 1、不必真正的删除数据节点，不然有可能超时，间接应用一个变量$occupied$保留，在遍历的时候不要拜访就好。
  • 2、每一次查问都得初始化$visited$数组，不然后果谬误。
  • 3、无向图得存储两边的数据，也就是得初始化$G[a][b] = G[b][a] = 1;$

提交后果：

AC代码：

#include <cstdio>#include <cstring>using namespace std;int G[1005][1005] = {};//邻接矩阵int occupied;// 待攻占的城市bool visited[1005] = {};//拜访标记数组int N,M,K;// 城市数目，门路条数，攻占的城市void DFS(int start){    visited[start] = true;    for (int i = 1; i <= N; ++i) {        if(G[start][i]!=0&&i!=occupied&&!visited[i]){            // 拜访所有与start连通，没有被攻占，并且没有被拜访的节点            DFS(i);        }    }}void DFSTraverse(){    int connected_component_count = 0;    for (int i = 1; i <= N; ++i) {        if(!visited[i]&&i!=occupied){// i不能是被攻占节点            DFS(i);            ++connected_component_count;        }    }    printf("%d\n",connected_component_count-1);}int main(){    scanf("%d %d %d",&N,&M,&K);    int a,b;    for (int i = 0; i < M; ++i) {        scanf("%d %d",&a,&b);        G[a][b] = G[b][a] = 1;    }    for (int j = 0; j < K; ++j) {        scanf("%d",&occupied);        memset(visited,0, sizeof(visited));        DFSTraverse();    }    return 0;}