1013.Battle Over Cities

【题意】

给出一些城市之间连接的道路，假如去掉某个城市，计算要使得剩下城市保持联通需要补上的道路数量

【思路】

去掉某个城市后，对剩下的城市进行DFS，根据DFS的次数算出共有几个连通分量，连通分量数-1即是需要补上的道路数

#include <iostream>
#include <cstring>
using namespace std;

#define MAXN 1000

int road[MAXN][MAXN],visited[MAXN];//visited表示在dfs中是否被访问到

void dfs(int j, int check, int n){
 visited[j] = 1;
 for(int i=0; i<n; i++){
  if(i!=j && i+1!=check && road[j][i] && !visited[i]){
   dfs(i,check,n);
  }
 }
}

int main(int argc, char const *argv[])
{
 int n,m,k,c1,c2;
 int check,count//check代表要检测的城市，count表示连通分量数目
 memset(road,0,sizeof(road));

 cin >> n >> m >> k;
 for(int i=0; i<m; i++){
  cin >> c1 >> c2;
  road[c1][c2] = road[c2][c1] = 1;
 }

 for(int i=0; i<k; i++){
  cin >> check;
  memset(visited,0,sizeof(visited));
  count = 0;
  for(int j=0; j<n; j++){
   if (j+1!=check && !visited[j])
   {
    count++;
    dfs(j,check,n);
   }
  }
  cout << count-1;
  if (i!=k-1)
  {
   cout << endl;
  }
 }

 system("pause");
 return 0;
}