1013 Battle Over Cities (25分) 圖的連通分量+DFS

題目

It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.

For example, if we have 3 cities and 2 highways connecting city1 -city2 and city1
-city3 . Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2 -city3 .

Input Specification:
Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.

Output Specification:
For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.

Sample Input:
3 2 3
1 2
1 3
1 2 3
Sample Output:
1
0
0

題目解讀

有n個城市，給出了其中幾個城市之間存在路徑（直接或間接），也就是連通，現在假設某個城市淪陷，和它有關聯的路徑全部斷開，問需要修幾條路才能保證剩下的城市全連通。相當於連通的城市組成一個集合，可能有好幾個這樣的集合，那麼n個集合需要n-1條路就能全部連通。也就是說，淪陷的城市，單獨作為一個集合，再去找出剩下的這些連通的集合，假如有n個，返回n-1即可。

給你一個無向圖，給定某個節點，把這個節點直接關聯的邊全斷開，然後去求連通分量的個數，最後返回連通分量的個數減1。

思路解釋

一般對於求連通分量的問題，都是並查集或者DFS，我這裡採用DFS，因為DFS是真的簡單。

用一個visit數組記錄節點的訪問狀況，初始化全部為false。
dfs(int i)內，完成把和i直接關聯或間接關聯的節點都標記為true（鄰接節點繼續遞歸找到的就是間接相關聯的），這樣，一次dfs就相當於一個連通分量從整個節點集中排除出去了，我們只需要統計dfs執行了多少次才使得visit數組全為false，就能得到連通分量的個數。
對於這個題，加入淪陷的城市是lost，本來應該把和它關聯的劃分到一起，但是因為它淪陷了，需要斷開全部路徑，我們只需要把visit[lost]單獨設置為false再去劃分別的，就能達到將他排除在外的效果。

滿分程式碼

注釋很詳細，大家自己看吧，啦啦啦。。。

#include <iostream>
#include <algorithm>
using namespace std;
/**
 * 有n個城市，給出了其中幾個城市直接存在路（直接或間接），也就是連通，
 * 現在假設某個城市淪陷，和它有關聯的路徑全部斷開，問需要修幾條路才能保證剩下的城市全連通
 *
 * 相當於連通的城市組成一個集合，可能有好幾個這樣的集合，那麼n個集合需要n-1條路就能全部連通
 *
 * 也就是說，淪陷的城市，單獨作為一個集合，再去找出剩下的這些連通的集合，假如有n個，返回n-1即可
 *
 */
// 鄰接矩陣，節點編號 1-1000
bool graph[1001][1001];
// 用是否訪問來劃分連通的集合
bool visit[1001];

// 有幾個城市
int g_nodes;

// 每一次dfs，都把和這個城市連通的所有城市標記為以訪問，這樣就相當於劃分出一個集合，統計這個函數執行了幾次就能知道劃分出了幾個集合
void dfs(int node) {
    // 標記自己
    visit[node] = true;
    // 找到和他連通的，且沒有標記過的，進行標記，劃分為一個連通集合
    for (int j = 1; j <= g_nodes; ++j) {
        if (!visit[j] && graph[node][j])
            // 注意這裡是深度優先遍歷，不是直接visit[j]=true,要找到全部直接或間接連連通的
            dfs(j);
    }
}

int main() {

    int edges, k;
    cin >> g_nodes >> edges >> k;
    int s, e;
    while (edges-- > 0) {
        cin >> s >> e;
        // 無向圖
        graph[s][e] = graph[e][s] = true;
    }
    // k種假設
    int lost;
    while (k-- > 0) {
        cin >> lost;
        // 重新初始化viste數組
        fill(visit, visit + g_nodes + 1, false);
        // 統計連通分量有幾個
        int cnt = 0;
        // 淪陷的城市單獨作為一個集合
        visit[lost] = true;
        // 統計剩下的連通分量有幾個
        for (int j = 1; j <= g_nodes; ++j) {
            // 它所在的連通分量還未被劃分並統計
            if (!visit[j]) {
                dfs(j);
                // 每一次dfs都會劃分出一個連通分量
                cnt++;
            }
        }
        // n集合，需要n-1個邊
        cout << cnt - 1 << endl;
    }
    return 0;
}

Tags: C++ C/C++ 數據結構與演算法演算法與數據結構 PTA