PAT 甲级 1013 Battle over cities DFS找连通分量

Solution：

这个题的大意是：在一个有n个结点（结点序号为1~n）的图中，有m条边。这时，我们去掉任意一个结点，我们要在剩下的图中形成一个连通图，最少需要多少条边。这道题可以转化为在去掉一个结点后，图的连通分量的个数，连通分量的个数cnt再减1就是最少需要增加的边的数量。
先把要去掉的结点从图中移除，即visit[v]=1，再进行dfs，每次dfs后cnt+1。
最后cnt-1就是结果。

代码如下：

//dfs 找连通分量
#include<iostream>
using namespace std;

bool visit[1005];
int mp[1005][1005];
int n,m,k;//n为城市个数，m为边的个数，k为要查询的城市个数

void dfs(int v){
  visit[v]=true;
  for(int i=1;i<=n;i++){
    if(visit[i]==false&&mp[v][i]==1){//如果有点没有访问且和v相连
        dfs(i);
    }
  }
}

int main(){
  while(cin>>n>>m>>k){
    for(int i=0;i<1005;i++){//初始化
        visit[i]=false;
    }

    for(int i=0;i<1005;i++){//初始化
        for(int j=0;j<1005;j++){
            mp[i][j]=0;
        }
    }

    int a,b;//边的两个点
    for(int i=0;i<m;i++){
        cin>>a>>b;
        mp[a][b]=mp[b][a]=1;
    }
    int v;//删除的点
    int cnt=0;
    for(int i=0;i<k;i++){
        cin>>v;
        visit[v]=true;
        for(int j=1;j<=n;j++){//dfs
            if(visit[j]==false){
                dfs(j);
                cnt++;
            }
        }
        cout<<cnt-1<<endl;//输出结果
        cnt=0;
        for(int i=0;i<1005;i++){//初始化
            visit[i]=false;
        }
    }
  }
  return 0;
}