UVa11709 - Trust groups(DFS、Kosaraju's Algorithm)

題目大意

由於公司內部的員工產生了不信任的問題導致公司生產力降低，為了解決此問題，因此公司決定讓互相信任的人組成一組，來增加生產力。
我們希望可以在公司的員工們，分成最小的組別數。

題目連結

重點觀念

• Kosaraju’s Algorithm by 大衞的筆記

分析

Kosaraju’s Algorithm 的模板題，直接套用即可。

參考連結

Uva11709 - Trust groups by txya900619
Component: Kosaraju’s Algorithm by 師大演算法

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 1020
#define int long long
using namespace std;
string a, b;
map<string, int> name;
vector<int> edge[MAXN];
vector<int> rev_edge[MAXN];
vector<int> path;
int visit[MAXN];
int group[MAXN];
int t, p, cnt;

void dfs1(int root){
    if(visit[root]) return;
    visit[root] = 1;

    for(auto it: edge[root]){
        dfs1(it);
    }
    path.push_back(root);
}

void dfs2(int root, int ancestor){
    if(visit[root]) return ;

    visit[root] = 1;
    group[root] = ancestor;
    for(auto it: rev_edge[root]){
       dfs2(it, ancestor);
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> p >> t && (t+p)!=0){
        cin.ignore();
        name.clear();
        cnt = 1;
        for(int i = 0; i < p; i++){ //清除資料，將名子進行 hash
            edge[cnt].clear();
            rev_edge[cnt].clear();

            getline(cin, a);
            name[a] = cnt++;
        }


        for(int i = 0; i < t; i++){
            getline(cin, a);
            getline(cin, b);
            edge[name[a]].push_back(name[b]); //題目圖
            rev_edge[name[b]].push_back(name[a]); //反向圖
        }

        memset(visit, 0, sizeof(visit));
        path.clear();

        for(int i = 1; i < cnt; i++){
            if(!visit[i]) dfs1(i);
        }

        int ans = 0; //總共有幾組 SCC
        memset(visit, 0, sizeof(visit));
        memset(group, 0, sizeof(group));
        for(int i = path.size()-1; i >= 0; i--){ 
            if(!visit[path[i]]){
                dfs2(path[i], path[i]);
                ans++;
            }
        }

        //for(int i = 1; i < cnt; i++){
        //    cout << i << " " << group[i] << "\n";
        //}
        cout << ans << "\n"; //輸出答案

    }
    return 0;
}