UVa12783 - Weak Links(DFS、Find Bridge Problem)

題目大意

警察想要拆除犯罪份子的聯繫，會給你一個犯罪分子的聯繫圖，只要我們能夠將這個聯繫圖一分為二，此時他們的消息傳播就會被我們給阻斷。

你的任務就是要找出只要切斷那些犯罪份子的聯繫，就可以讓消息傳播阻斷，輸出總共有幾種切法，並且輸出每一種切法。
並且從最小的犯罪份子(數字代號)開始依序輸出
題目連結

重點觀念

• Find Bridge Problem

分析

• 首先，我們知道，將圖一分為二的方法就是找到 bridge
• 因此我們就將所有的 bridge 存在 vector
• 之後 vector sort 就可以輸出。
• 這篇則有詳細的說明 Find Bridge Problem by 大衞的筆記

參考連結

• Find Bridge Problem
• Uva12783 - Weak Links by txya900619

心得

有時候不要耍小聰明，想說少寫一兩行，少做一個 step，將一些步驟優化掉，一定要先確認這個絕對沒錯，才可以優化！

不然就會像我一樣，為了除一個錯，花了一個小時…，雖然我是覺得當你認為你優化非常棒的時候，就不會覺得有錯XD，好矛盾喔www。

總之就是，要想清楚再寫，盡量想到各種可能性，沒想到地就當經驗，吸收起來。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。
其中 Find Bridge Problem by 大衞的筆記 這邊的程式碼請看這個 link 有詳細的說明。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define MAXN 1200
#define int long long
using namespace std;
vector<int> edge[MAXN];
vector<pair<int,int> > bridge; //儲存 bridge
int visit[MAXN], depth[MAXN], low[MAXN];
int n, m, a, b;

void find_bridge(int root, int past, int cnt){
    visit[root] = 1; //表示走訪過
    depth[root] = low[root] = cnt; //邏輯證明 2.1

    for(int node: edge[root]){ //不斷遍地
        //因為是無向邊，因此雙向同個 edge 不是 bridge
        if(node == past) continue;
        if(visit[node]) low[root] = min(low[root], depth[node]); //邏輯證明 2.2
        else{
            //先進行 DFS，往下找其他的 node 有沒有辦法回到曾經走放過的節點
            find_bridge(node, root, cnt+1);

            low[root] = min(low[root], low[node]); //邏輯證明 2.3

            if(low[node] > depth[root]){  //邏輯證明 2.4
                //我的 bug，請引以為戒。
                //我原本想說按照題目要求，小的放前面。那我就先使用 if 如果 root > node 就交換，
                //但這樣會造成接下來的 for 中 root 全部都是錯的！
                //請大家不要跟我一樣犯錯...
                //if(node < root) swap(node, root); 

                //小的節點放前面，大的放後面
                bridge.push_back({min(node, root), max(node, root)}); 
            }
        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> m && (n+m) != 0){
        bridge.clear();
        memset(visit, 0, sizeof(visit));
        memset(depth, 0, sizeof(depth));
        memset(low, 0, sizeof(low));
        for(int i = 0; i < n; i++) edge[i].clear();

        for(int i = 0; i < m; i++){
            cin >> a >> b;
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        for(int i = 0; i < n; i++){
            if(!visit[i]) find_bridge(i,-1, 0);
        }

        sort(bridge.begin(), bridge.end());
        cout << bridge.size();
        for(auto b: bridge){
            cout << " " << b.first << " " << b.second;
        }
        cout << "\n";

#ifdef DEBUG
        for(int i = 0; i < n; i++){
            cout << "i depth low " << i << " " << depth[i] << " " << low[i] << "\n";
        }
        for(int n: edge[8]) cout << n << " ";
        cout << "\n";
#endif
    }
    return 0;
}