PTA甲級1013 DFS算法

題目

大意：

若幹個城市之間有若幹條道路。如果某個城市被敵人攻占，那麼通向該城市的道路就被關閉。為了使所有的城市連通，求還需要建設幾條道路。

思路：使用dfs算法檢視未連通的路徑及有幾條連通路徑即可

代碼

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1111;
vector<int> g[N];//鄰接表
bool vis[N];//标記各頂點是否被标記

int current;//目前需要删除的頂點編号
//dfs(v)dfs周遊v所有連通
void dfs(int v){
    if(v == current) return;
    vis[v] = true;
    for(int i = 0;i<g[v].size();i++){
        if(vis[g[v][i]] == false)
        dfs(g[v][i]);
    }
}

int n,m,k;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int q = 0;q<k;q++){//k次查詢
        scanf("%d",&current);//删除的頂點編号
        memset(vis,false,sizeof(vis));//初始化vis數組為false；
        int block = 0;
        for(int i = 1;i <= n;i++){
            if(i!=current && vis[i] == false){//如果該點沒被通路過
                dfs(i);
                block++;
            }
        }
        printf("%d\n", block-1);
    }
    return 0;
}