This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100007;
int n, m;
vector<int> gr[MAXN];
bool vis[MAXN];
int dsu[MAXN], sz[MAXN];
void init(int n) { for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1; }
int get(int i) { return (i == dsu[i] ? i : dsu[i] = get(dsu[i])); }
bool same(int i, int j) { return get(i) == get(j); }
void join(int i, int j) { i = get(i), j = get(j); if (i == j) return; if (sz[i] < sz[j]) swap(i, j); sz[i] += sz[j], dsu[j] = i; }
void dfs(int);
void add(int u, int v)
{
bool redfs = (!vis[v] || sz[get(v)] == 1);
join(u, v);
if (redfs) dfs(v);
}
void dfs(int u)
{
vis[u] = 1;
if (sz[get(u)] > 1) for (int v : gr[u]) add(u, v);
else if ((int) gr[u].size() == 1) {
if (!vis[gr[u][0]]) dfs(gr[u][0]);
} else if (gr[u].empty()) {}
else {
add(gr[u].back(), gr[u].front());
for (int v : gr[u]) if (v != gr[u].front()) add(gr[u].front(), v);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
gr[u].push_back(v);
}
init(n + 1);
for (int u = 1; u <= n; ++u) if (!vis[u]) dfs(u);
long long ans = 0;
for (int u = 1; u <= n; ++u) for (int v : gr[u]) {
if (!same(u, v)) ++ans;
}
for (int u = 1; u <= n; ++u) if (u == get(u)) ans += 1ll * sz[u] * (sz[u] - 1);
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |