UVa11770 - Lighting Away(DFS、Tarjan's Algorithm)

題目大意

Ronju 是一個保全，他每天晚上都必須讓公園裡的所有燈開啟，為此他必須每個電燈都走過去並開啟，他覺得太麻煩了，因此他買了許多不良但價格便宜的光感追蹤器，這種光感追蹤器很酷，只要他感應到 A 的電燈有開，則 B 也會開啟。

現在會給你已知的資訊，只要 A 被點亮，同時 B 也會開啟的光感追蹤器數組，請告訴 Ronju 自己必須去手動開幾個電燈才可以把公園裡的全部電燈打開

題目連結

重點觀念

• Tarjan’s Algorithm by 大衞的筆記
• 找到每個 SCC 後，確認是否可以讓兩個 SCC 被連通。

分析

• 首先，先做一次 Tarjan’s Algorithm
• 假如有兩個 SCC 是可以透過一個 bridge 連通，那是不是只要點一個燈，就可以讓兩個 SCC 連起來了，那我要怎麼排除這種情況
  • 對所有的節點連接的每個連接都檢查一次
    • it 為 A 開啟則 B 會開啟中的 B
    • root 為 A 開啟則 B 會開啟中的 A
  • 首先我們知道，如果 lead[it] != it 表示，這一個 SCC 的老大並不是 it
  • 如果 lead[it] != lead[root]，表示他們是兩個不同的 SCC，但卻可以互相連接，因此我們就可以讓 lead[it] 這組 SCC 不用被開啟，因為它可以被 lead[root] 開啟

參考連結

Component: Tarjan’s Algorithm by 師大演算法
11770 - Lighting Away by morris821028

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 10020
using namespace std;
int t, n, m, a, b, kase=1, cnt;
vector<int> edge[MAXN];
int stk[MAXN], in_stk[MAXN];
int visit[MAXN];
int lead[MAXN], low[MAXN];
int follow[MAXN]; //follow 如果數值大於等於 1 表示，這個電燈可以被另外一個電燈給開啟。
int stk_index;

void scc(int root){
    if(visit[root]) return;

    visit[root] = low[root] = cnt++;
    stk[++stk_index] = root;
    in_stk[root] = 1;

    for(auto it: edge[root]){
        scc(it);
        if(in_stk[it]) low[root] = min(low[it], low[root]);
    }

    if(visit[root] == low[root]){
        int it;
        do{
            it = stk[stk_index--];
            in_stk[it] = 0;
            lead[it] = root;
        }while(it != root);
    }
}

void isfollow(int root){
    for(auto it: edge[root]){
        if(lead[it] != it) follow[it]++;
        if(lead[root] != lead[it]) follow[lead[it]]++; //如果可以從 A強通道走道 B 強通道，就刪掉 B 強通道的開燈點
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++){ //清除資料
            edge[i].clear();
        }

        for(int i = 1; i <= m; i++){ //加入邊
            cin >> a >> b;
            edge[a].push_back(b);
        }

        memset(visit, 0, sizeof(visit));
        for(int i = 1; i <= n; i++){ //進行 tarjan
            if(visit[i]) continue;
            stk_index = -1; cnt = 1;
            scc(i);
        }
        //cout << "banana\n";


        memset(follow, 0, sizeof(follow));
        for(int i = 1; i <= n; i++) isfollow(i);

        int ans = 0;
        for(int i = 1; i <= n; i++){
            //如果沒有辦法被其他電燈給開啟就 ans++
            if(!follow[i] && lead[i] == i) ans++; 
            //其中 lead[i] == i 則是此電燈沒辦法被其他電燈開啟，表示他會是強通道
        }

        //for(int i = 1; i <= n; i++) cout << i << " " << group[i] << "\n";
        cout << "Case " << kase++ << ": " << ans << "\n";

    }
    return 0;
}