#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, m;
int p[N];
int sz[N];
set<int> in[N], out[N];
int par(int v) {
return p[v] == v ? v : p[v] = par(p[v]);
}
bool unite(int a, int b) {
a = par(a);
b = par(b);
if (a == b || !out[a].count(b) || !out[b].count(a)) return false;
if (sz[a] > sz[b]) swap(a, b);
sz[b] += sz[a];
out[a].erase(b);
out[b].erase(a);
in[a].erase(b);
in[b].erase(a);
p[a] = b;
vector<pair<int, int>> to;
for (int v : out[a]) {
in[v].erase(a);
in[v].insert(b);
if (in[b].count(v)) to.push_back({b, v});
out[b].insert(v);
}
out[a].clear();
for (int v : in[a]) {
out[v].erase(a);
out[v].insert(b);
if (out[b].count(v)) to.push_back({b, v});
in[b].insert(v);
}
in[a].clear();
for (auto t : to) unite(t.first, t.second);
return true;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
p[i] = i, sz[i] = 1;
while (m--) {
int a, b;
cin >> a >> b;
a = par(a);
b = par(b);
if (a != b) {
out[a].insert(b);
in[b].insert(a);
unite(a, b);
}
ll sum = 0;
for (int i = 1; i <= n; i++) {
if (p[i] == i) {
sum += (ll)sz[i] * (sz[i] - 1);
for (int v : out[i]) sum += (ll)sz[i] * sz[v];
}
}
cout << sum << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
