程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 11709 Trust groups （強連通分量）

UVA - 11709 Trust groups （強連通分量）

編輯：C++入門知識

UVA - 11709 Trust groups （強連通分量）

求強連通分量的個數。

#pragma comment(linker, /STACK:10240000,10240000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#define mod 4294967296
#define MAX 0x3f3f3f3f
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
#define SZ(x) ((int)ans.size())
#define MAKE make_pair
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define mem(a) memset(a, 0, sizeof(a))
const double pi = acos(-1.0);
const double eps = 1e-9;
const int N = 100005;
const int M = 20005;
typedef long long ll;
using namespace std;

int n, m;
vector  G[N];
int pre[N], low[N], scc[N], dfs_clock, scc_cnt;
stack  S;
int T;
void dfs(int u) {
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(pre[v] == 0) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if(scc[v] == 0) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]) {
        scc_cnt++;
        for(;;) {
            int x = S.top(); S.pop();
            scc[x] = scc_cnt;
            if(x == u) break;
        }
    }
}
void find_scc() {
    dfs_clock = scc_cnt = 0;
    mem(scc);
    mem(pre);
    for(int i = 0; i < n; i++) {
        if(pre[i] == 0) dfs(i);
    }
}
map  mp;
int main()  {

    //freopen(in.txt,r,stdin);
    while(cin >> n >> m && n + m) {

        for(int i = 0; i < n; i++) {
            G[i].clear();
        }
        string s, t;
        for(int i = 0; i < n; i++) {
            cin >> s >> t;
            mp[s+t] = i;
        }
        for(int i = 0; i < m; i++) {
            cin >> s >> t;
            int x = mp[s+t];
            cin >> s >> t;
            int y = mp[s+t];
            G[x].push_back(y);

        }

        find_scc();

        cout << scc_cnt << endl;

    }

    return 0;
}