UVa12363 - Hedge Mazes(DFS、Find Bridge Problem、Disjoint Set)

題目大意

女王是迷宮粉絲，因此他把女王的住處切割成每一個房間，並透過走廊連接，每一個房間都透過走廊連接，女王想問你說從 A 到 B 是不是恰好只有一條路徑可以抵達。

題目連結

重點觀念

• Find Bridge Problem
• 並查集
• 必須先熟悉上面兩點才有辦法寫此題目

分析

• 首先，我們知道，如果要恰好只有一條路徑，那麼就必須每一個走廊都要是 bridge 才有辦法完成。
• 因此，我們用 Find Bridge Problem + disjoint set 將所有的橋都放在同個 set。
• 這篇則有詳細的說明 Find Bridge Problem by 大衞的筆記

參考連結

Uva12363 - Hedge Mazes by txya900619
Finding bridges in a graph in O(N+M) by CP-alhorithm

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define DEBUG
#define int long long
#define MAXN 100020
using namespace std;
vector<int> edge[MAXN];
int visit[MAXN], ancestor[MAXN];
int depth[MAXN], low[MAXN];
int r, c, q, cnt;
int a, b;

int find_root(int x){
    if(ancestor[x] != x) return ancestor[x] = find_root(ancestor[x]);
    return ancestor[x];
}

void find_bridge(int root, int past){
    visit[root] = 1;
    depth[root] = low[root] = cnt++;
    for(int node: edge[root]){
        if(node == past) continue;
        if(visit[node]) low[root] = min(low[root], depth[node]);
        else{
            find_bridge(node, root);
            low[root] = min(low[root], low[node]);
            if(low[node] > depth[root]){
                int fa_node = find_root(node);
                int fa_root = find_root(root);
                //cout << "fa " << fa_node << " " << fa_root << "\n";
                ancestor[fa_node] = fa_root;
            }
        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> r >> c >> q && (r+c+q) != 0){
        for(int i = 1; i <= r; i++){
            edge[i].clear();
            ancestor[i] = i;
        }
        memset(visit, 0, sizeof(visit));
        memset(depth, 0, sizeof(depth));

        for(int i = 0; i < c; i++){
            cin >> a >> b;
            edge[a].push_back(b);
            edge[b].push_back(a);

        }

        cnt = 1;
        for(int i = 1; i <= r; i++){
            if(!visit[i]) find_bridge(i, -1);
        }

#ifdef DEBUG
        for(int i = 1; i <= r; i++){
            cout << "ancestor " << i << " " << ancestor[i] << "\n";
        }
        for(int i = 1; i <= r; i++){
            cout << "low " << i << " " << low[i] << "\n";
        }
#endif

        while(q--){
            cin >> a >> b;
            int fa_a = find_root(a);
            int fa_b = find_root(b);
            if(fa_a == fa_b) cout << "Y\n"; //如果在同個 bridge node 就是 Yes
            else cout << "N\n"; //沒有表示有兩種以上路徑 or 沒有路徑
        }
        cout << "-\n";
    }
    return 0;
}