#include <bits/stdc++.h>
using namespace std;
#define int long long
#define siz(x) (int)x.size()
const int N = 100005;
int p[N], sz[N], ans = 0;
map<pair<int, int>, int> mp;
vector<int> vt[N];
set<int> st[N], g1[N], g2[N];
int find(int u) {
return p[u] == u ? u : p[u] = find(p[u]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (siz(g1[u]) + siz(g2[u]) < siz(g1[v]) + siz(g2[v])) swap(u, v);
p[v] = u;
sz[u] += sz[v];
for (int i : g1[v]) {
g2[i].erase(v);
if (find(i) != find(u)) {
g2[i].insert(u);
g1[u].insert(i);
mp[{u, i}] += mp[{v, i}];
}
mp[{v, i}] = 0;
}
g1[v].clear();
for (int i : g2[v]) {
g1[i].erase(v);
if (find(i) != find(u)) {
g1[i].insert(u);
g2[u].insert(i);
mp[{i, u}] += mp[{i, v}];
}
mp[{i, v}] = 0;
}
g2[v].clear();
for (int i : st[v]) if (find(u) != find(i)) st[u].insert(i);
st[v].clear();
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
while (m--) {
int u, v;
cin >> u >> v;
if (st[find(v)].count(u)) { // need to delete?
cout << ans << '\n';
continue;
}
if (find(u) != find(v)) st[find(v)].insert(u);
u = find(u), v = find(v);
if (u == v) {
cout << ans << '\n';
continue;
}
mp[{u, v}]++;
g1[u].insert(v);
g2[v].insert(u);
ans += sz[v];
if (g1[v].count(u)) {
ans += sz[u] * sz[v] * 2;
// cout << ans << '\n';
// ans += (siz(st[u]) - mp[{v, u}]) * sz[v];
ans += (siz(g2[u]) - (mp[{v, u}])) * sz[v]; // change to sum of sizes of followers..
// cout << ans << '\n';
// ans += (siz(st[v]) - mp[{u, v}]) * sz[u];
ans += (siz(g2[v]) - (mp[{u, v}])) * sz[u];
// cout << ans << '\n';
ans -= mp[{u, v}] * sz[v];
// cout << ans << '\n';
ans -= mp[{v, u}] * sz[u];
// cout << ans << '\n';
merge(u, v);
}
cout << ans << '\n';
// for (auto [pr, val] : mp) cout << pr.first << ' ' << pr.second << ' ' << val << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
