PAT (Advanced Level) Practice 1013 Battle Over Cities (25分)-蒲公英云

PAT (Advanced Level) Practice 1013 Battle Over Cities (25分)

题意：一个连通图，删除一个结点后，至少连几条线可以将图再次还原成联连通图。显然，两个连通分量要一条，三个连通分量要两条，….N个连通分量要N-1条。深度优先搜索最外层的循环可判断到底有几个连通分量。

#include <iostream>
#include<stdio.h>
#define maxn 1001
using namespace std;
int G[maxn][maxn]={0};
int temp[maxn][maxn]={0};
bool visited[maxn]={false};
int N,M,K;
void dfs(int index){
    visited[index] = true;
    for(int i=1;i<=N;i++){
        if(visited[i]==false&&temp[index][i]==1){
            dfs(i);
        }
    }
}
int check(int city){
    for(int i=1;i<=N;i++){
            visited[i] = false;
        for(int j=1;j<=N;j++){
            temp[i][j] = G[i][j];
        }
    }
    for(int i=1;i<=N;i++){
        temp[i][city] =temp[city][i] = 0;
    }
    int turn = 0;
    visited[city] = true;
    for(int i=1;i<=N;i++){
        if(visited[i]==false){
            turn++;
            dfs(i);
        }
    }
    return turn;
}
int main()
{
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<M;i++){
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        G[v1][v2] = G[v2][v1] = 1;
    }
    for(int i=0;i<K;i++){
        int check_city;
        scanf("%d",&check_city);
        printf("%d\n",check(check_city)-1);
    }
    return 0;
}