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 <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define DEBUG(x) { cerr << #x << '=' << x << endl; }
#define Arr(a, l, r) { cerr << #a << " = {"; FOR(_, l, r) cerr << ' ' << a[_]; cerr << "}\n"; }
#define N 1001000
#define pp pair<int, int>
#define endl '\n'
#define IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define taskname ""
#define bit(S, i) (((S) >> (i)) & 1)
using namespace std;
int visited[N], f[N], n;
vector<int> e[N];
int root(int u) { return f[u] < 0 ? u : (f[u] = root(f[u])); }
void Union(int a, int b){
a = root(a), b = root(b);
if (a == b) return;
int t = f[a] + f[b];
if (f[a] > f[b]) swap(a, b);
f[a] = t;
f[b] = a;
}
int cnt;
void dfs(int u) {
cnt++;
DEBUG(u);
visited[u] = 1;
for (int v : e[u]) if (!visited[v]) {
Union(u, v);
dfs(v);
}
}
int main() {
#ifdef NERO
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
#endif //NERO
IO;
int m;
cin >> n >> m;
REP(i, m) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
FOR(u, 1, n) f[u] = -1;
long long ans = 0;
FOR(u, 1, n) if (!visited[u]) {
cnt = 0;
if (e[u].size() > 1) {
int r = -1;
for (int v : e[u]) {
if (r != -1) Union(r, v);
else r = v;
dfs(v);
}
}
// DEBUG(cnt);
}
//Arr(f, 1, n);
FOR(u, 1, n) if (f[u] < 0) ans += 1ll * f[u] * (f[u] + 1);
FOR(u, 1, n) {
for (int v : e[u]) if (root(u) != root(v)) ans++;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |