Uva11709 - Trust groups

題目大意

公司內部有些信任上的問題，所以公司組成一個全部互相信任的人所組成的團隊，這個團隊越小越好

重點觀念

• 強連通

分析

• Kosaraju
• 輸入需要一次輸入一行

程式題目碼

#include <iostream>
#include <map>
#include <vector>

using namespace std;

vector<int> graph[1010];
vector<int> rev_graph[1010];
bool vis[1010];
vector<int> ans;

void dfs(int cur) {
    vis[cur] = true;
    for (auto i : graph[cur]) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    ans.push_back(cur);
}

void rev_dfs(int cur) {
    vis[cur] = false;
    for (auto i : rev_graph[cur]) {
        if (vis[i]) {
            rev_dfs(i);
        }
    }
}

void reset() {
    for (int i = 0; i < 1010; i++) {
        graph[i].clear();
        rev_graph[i].clear();
        vis[i] = false;
    }
    ans.clear();
}

int main() {
    int p, t;
    while (cin >> p >> t, p > 0) {
        getchar();
        map<string, int> person;
        reset();
        for (int i = 0; i < p; i++) {
            string name;
            getline(cin, name);
            person[name] = i;
        }

        for (int i = 0; i < t; i++) {
            string a_name;
            string b_name;
            getline(cin, a_name);
            getline(cin, b_name);

            graph[person[a_name]].push_back(person[b_name]);
            rev_graph[person[b_name]].push_back(person[a_name]);
        }

        int cnt = 0;

        for (int i = 0; i < p; i++) {
            if (!vis[i]) {
                dfs(i);
            }
        }

        for (auto i = ans.rbegin(); i != ans.rend(); i++) {
            if (vis[*i]) {
                rev_dfs(*i);
                cnt++;
            }
        }

        cout << cnt << endl;
    }

    return 0;
}