1013. Battle Over Cities (25)

这题给定了一个图，我用DFS的思想，来求出在图中去掉某个点后还剩几个相互独立的区域（连通子图）。

在DFS中，每遇到一个未访问的点，则对他进行深搜，把它能访问到的所有点标记为已访问。一共进行了多少次这样的搜索，

就是我们要求的独立区域的个数。

#include <iostream>  
#include <fstream>  
#include <memory.h>  
using namespace std;  
  
const int maxNum = 1001;  
  
bool visited[maxNum];  
int edge[maxNum][maxNum];  
int N, M, K;  
  
void DFS(int begin)  
{  
    for(int i = 1; i <= N; i++)  
    {  
        if(edge[begin][i] && !visited[i])  
        {  
            visited[i] = true;  
            DFS(i);  
        }  
    }  
}  
  
int main()  
{  
    //fstream cin("a.txt");  
  
    cin>>N>>M>>K;  
    for(int i = 1; i <= M; i++)  
    {  
        int tmp1, tmp2;  
        cin>>tmp1>>tmp2;  
        edge[tmp1][tmp2] = edge[tmp2][tmp1] = 1;  
    }  
    memset(visited, 0, maxNum);  
  
    int result = 0;  
    for(int i = 0; i < K; i++)  
    {  
        int k;  
        cin>>k;  
        visited[k] = true;  
        for(int j = 1; j <= N; j++)  
        {  
            if(!visited[j])  
            {  
                DFS(j);  
                result++;  
            }  
        }  
        cout<<result - 1<<endl;  
        memset(visited, 0, maxNum);  
        result = 0;  
    }  
}

补充：软件开发 , C++ ,