关于算法-数据结构:PAT甲级1013-Battle-Over-Cities

题目粗心：

给定 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;
}