算法
(BFS) $O(n(n + m))$
只需检验任意两点是否连通即可,具体可以通过跑 $n$ 次 $\rm BFS$ 来实现。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
}
int ans = 0;
rep(sv, n) {
queue<int> q;
vector<int> used(n);
used[sv] = 1;
++ans;
q.push(sv);
while (q.size()) {
int v = q.front(); q.pop();
for (int u : to[v]) {
if (used[u]) continue;
++ans;
used[u] = 1;
q.push(u);
}
}
}
cout << ans << '\n';
return 0;
}