深度优先搜索遍历(Deepth First Search:DFS)

解决图连通问题的经典方法就有DFS，下面以PAT  1013. Battle Over Cities 为例：

1、该题的问题归纳为：存在n个城市，相互之间有道路连通的城市共有m组，如果其中一个城市被敌军占领，要修多少条路才能重新恢复连通状态？

2、这里，当某城市被占领时，与其相连的道路将断开，如果不是一个全通图，这里必然会出现不存在交集的连通图，对这些连通图用最少的线重新连起来就能恢复连通状态。

3、考虑使用DFS的主要原因是：在标志区域性连通图的过程中，深度优先搜索遍历可以确保从其中一个点出发找出该点能达到的所有地方，因而可以使用DFS查找连通区域的个数，恢复全图连通状态的连线数就是区域数减一。

给出代码如下（有测试用例超时）

#include<iostream>
#include<algorithm>


using namespace std;

int n;
bool visit[1001];
int v[1001][1001];
void dfs(int node)
{
  visit[node] = true;
  
  for(int j = 1;j<=n;j++)
  if(visit[j]==false&&v[node][j]==1) 
    dfs(j);
}

int main(void)
{
  int m,k,a,b;
  cin>>n>>m>>k;
  for(int i=1;i<=m;i++)
    {
      cin>>a>>b;
      v[a][b] = 1;
      v[b][a] = 1;
    }
  for(int j = 1;j<=k;j++)
  {
    int temp = 0;
    cin>>temp;
        fill(visit,visit+1001,false);
    visit[temp] = true;

    int cnt = 0;
    for(int i = 1;i<=n;i++)
      if(visit[i]==false)
      {
        dfs(i);
        cnt++;
      }
      cout<<cnt-1<<endl;
  }
    return 0;
  
  
}