?
求强连通分量的个数。
#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; }