PAT_甲級_1013 Battle Over Cities (25分) (C++)【DFS+連通分量】

目錄

​​1，題目描述​​

​​題目大意​​

​​輸入​​

​​輸出​​

​​注意​​

​​2，思路​​

​​連通分量​​

​​定義​​

​​求法​​

​​核心思想​​

​​3，代碼​​

1，題目描述

Sample Input:

3 2 3
1 2
1 3
1 2 3      

Sample Output:

1
0
0      

題目大意

舉個例子吧（題目給出的）：

假設有3個城市c1，c2，c3，兩座橋b1，b2。若b1連接配接c1和c2，b2連接配接c1和c3，此時城市c1被占領，那麼與c1有關的道路全部被封鎖，要使其他兩個城市保持聯通，需要在c2與c3間建立橋梁。

輸入

第一行：N：the total number of cities，M：the number of remaining highways（剩餘的路的數量），K：the number of cities to be checked（我們關心的城市的數量）

中間M行：表示路連接配接的兩個城市的編号

最後一行：表示我們關心哪K個城市；

輸出

對每個城市來說，若這個城市被占領，則保持其他城市暢通，需要修多少條路；

注意

1. 城市編号：1-N（N<1000)；
2. 關心的城市即假設被占領的城市，在DFS算法之前就已經被标記為已通路；
3. 最後一個測試點總是逾時：上網檢視了下其他大神的解法​​@Joyceyang_999【甲級PAT 1013 Battle Over Cities(用cin始終最後一個測試運作逾時來看)】​​，以下為摘抄内容。

• 發現這裡一定要用scanf輸入而不是用cin輸入。對于大量輸入的操作，cin因為有同步機制是以會逾時。這裡有兩種辦法：
• 一、取消cin與stdin同步，在代碼間添加ios::sync_with_stdio(false);即可
• 二、改用scanf輸入

2，思路

簡單的說就是求圖中的聯通分量的個數；

而且對每個關心的城市，都要計算一次；

連通分量

定義

​​無向圖​​G的極大連通子圖稱為G的連通分量( Connected Component)。任何​​連通圖​​​的連通分量隻有一個，即是其自身，非連通的​​無向圖​​有多個連通分量。

求法

核心思想

3，代碼

#include<iostream>
using namespace std;

bool visited[1000];
bool graph[1000][1000];
int n, m, k;

void dfs(int start){
    visited[start] = true;
    for(int i = 1; i <= n; i++){    //i<=n
        if(visited[i] == false && graph[start][i] == true){
            dfs(i);
        }
    }
}

int main(){
//#ifdef ONLINE_JUDGE
//#else
//    freopen("1.txt", "r", stdin);
//#endif

    scanf("%d%d%d", &n, &m, &k);

    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        graph[a][b] = graph[b][a] = true;
    }

    for(int i = 0; i < k; i++){
        int city, num = 0;
        scanf("%d", &city);
        fill(visited, visited+n+1, false);
        visited[city] = true;

        for(int j = 1; j <= n; j++){//城市編号從1開始 且i<=n
            if(visited[j] == false){
                dfs(j);
                num += 1;
            }
        }
        printf("%d\n", num-1);
    }

    return 0;
}