# [CCF CSP201709-4通信网络]缩点+拓扑+bitset

xiaoxiao2021-02-28  4

# [CCF CSP201709-4通信网络]缩点+拓扑+bitset

## 1. 题目链接

[CCF CSP201709-4通信网络]缩点+拓扑

## 4. 实现代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f; const ll infl = 0x3f3f3f3f3f3f3f3fLL; template<typename T> inline void umax(T &a, T b) { a = max(a, b); } template<typename T> inline void umin(T &a, T b) { a = min(a, b); } const int MAXN = 1005; vector<int> T[MAXN], G[2][MAXN]; bitset<MAXN> bs[2][MAXN], okay; int n, m; int Low[MAXN], DFN[MAXN], Stack[MAXN], Belong[MAXN]; //Belong 数组的值是 1~scc int Index, top; int scc;//强连通分量的个数 bool Instack[MAXN]; void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for (int i = 0; i < T[u].size(); ++i) { int v = T[u][i]; if (!DFN[v]) { Tarjan(v); if (Low[u] > Low[v]) Low[u] = Low[v]; } else if (Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if (Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; } while (v != u); } } int du[2][MAXN]; void topu(int f) { for (int i = 1; i <= scc; ++i) { for (int e = 0; e < G[f][i].size(); ++e) { int j = G[f][i][e]; ++ du[f][j]; } } queue<int> q; for (int i = 1; i <= scc; ++i) { bs[f][i][i] = 1; if (!du[f][i]) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[f][u].size(); ++i) { int v = G[f][u][i]; -- du[f][v]; bs[f][v] |= bs[f][u]; if (du[f][v] != 0) continue; q.push(v); } } } int main() { #ifdef ___LOCAL_WONZY___ freopen("input.txt", "r", stdin); #endif // ___LOCAL_WONZY___ int u, v; cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> u >> v; // G[0][u].push_back(v); // G[1][v].push_back(u); T[u].push_back(v); } Index = scc = top = 0; for (int i = 1; i <= n; ++i) { if (!DFN[i]) Tarjan(i); } for (int i = 1; i <= n; ++i) { for (int e = 0; e < T[i].size(); ++e) { int j = T[i][e]; if (Belong[i] == Belong[j]) continue; G[0][Belong[i]].push_back(Belong[j]); G[1][Belong[j]].push_back(Belong[i]); } } for (int i = 1; i <= scc; ++i) { sort(G[0][i].begin(), G[0][i].end()); G[0][i].erase(unique(G[0][i].begin(), G[0][i].end()), G[0][i].end()); sort(G[1][i].begin(), G[1][i].end()); G[1][i].erase(unique(G[1][i].begin(), G[1][i].end()), G[1][i].end()); } topu(0); topu(1); for (int i = 1; i <= scc; ++i) { if (okay[i]) continue; bs[0][i] |= bs[1][i]; int a = bs[0][i].count(); if (a == scc) okay[i] = true; } int ans = 0; for (int i = 1; i <= n; ++i) { if (okay[Belong[i]]) ++ ans; } printf("%d\n", ans); #ifdef ___LOCAL_WONZY___ cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl; #endif // ___LOCAL_WONZY___ return 0; }