题目

解题思路

本题的考察的点就是连通分量的个数问题，想要解决这个问题，得知道一个知识：

• 如果当前有5个城市，且每个城市之间不互通，即5个独立的连通分量，那么需要4条边就可以将其连通。

本题就是考察，当一个城市消失后，其所在的边也会跟着消失，那么需要修几条路可以让其他城市连通起来，比如：

• 当前有5个顶点，有5条边，分别为1—2，2—3，3—4，3—5，1—3。那么现在失去3号顶点，那么其所在的边也要失删除，那么需要添加几条边使得剩下的顶点可以连通。发现，删除3号顶点后，只剩下3个连通分量，分别为，1—2，4，5。那么需要修两条边就可以使其连通。

这就是本题的一个思路，通过用dfs求连通图数量得出需要修建的公路数。

实现代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<sstream>
#include<algorithm>
using namespace std;

constexpr auto MAXN = 1001;

int G[MAXN][MAXN];
bool vis[MAXN];     //标记数组，用来标记是否访问过该顶点
int N,num,M;
int temp,cnt=0;

//DFS深度优先遍历
void DFS(int v)
{
    vis[v]=true;
    for(int i=1;i<=N;i++)
    {
        //当前节点是否被访问过以及从顶点v出发，是否有到顶点i的边
        //一定要给是未访问过的节点，如果访问过的节点，你再访问，连通分量的个数就会算重复
        if(vis[i]==false && G[v][i]==1)
            DFS(i);
    }
}

int main()
{
#ifdef ONLINE_JUDGE                
#else    
    freopen("1.txt", "r", stdin);
#endif 

    cin>>N>>num>>M;

    int a,b;
    for(int i=0;i<num;++i)
    {
        cin >> a >>b;
        G[a][b]=G[b][a]=1;  //无向图
    }

    //这个循环表示对题目给定的M个数进行处理
    for(int i=0;i<M;++i)
    {
        cin >> temp;

        //cnt一定要在这里给一个初始化，注意一下，我设置的是全局变量
        //因为每次接受一个被军队占领的城市，也就是该顶点要删除，我们要计算删除该顶点后，需要修建的公路
        //然后接受下一个的时候是要复原的，也就是按初始图的样子进行操作，所以cnt置零
        cnt=0;              

        //这个和cnt一个道理，要复原，那么vis标记数组就得刷新。temp的每个取值是独立的，不是相关的（题目要求）
        fill(vis,vis+MAXN,false);

        //这一步我解释一下，正常我们dfs遍历图，或者求连通分量个数，是在for和if中间加这句代码的
        //那这里把这句代码放这个位置其实就是模拟该顶点被删除的意思，即该城市被占领
        //因为把该顶点置为true，就意味着该顶点不会调用dfs，就是说该顶点不会被作为起点，那么自然也就不会去遍历从该顶点出发的所有边，所以这一步很重要
        vis[temp]=true;

        //这个for循环表示当前删除的顶点下，从其他顶点出发分别对其进行dfs
        for(int j=1;j<=N;++j)
        {
            if(vis[j]==false)
            {   
                //这里就基本操作，从顶点j出发，遍历其可以到达且未被访问过的顶点，然后每调用一次dfs函数，cnt++，表示从该顶点出发是有一个连通分量的
                DFS(j);
                cnt++;              //一定是放在这里++，而不是放到if外面
            }
        }

        cout<<cnt-1<<endl;
    }

    return 0;
}