#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
struct MEGA_DSU {
map<pair<int, int>, int> w;
set<int> children[N];
vector<int> p, sz;
void init() {
p.resize(N);
iota(p.begin(), p.end(), 0);
sz.resize(N, 1);
}
int get(int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
void merge(int u, int v) {
u = get(u);
v = get(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
}
ll ans;
void combine(int u, int v) {
u = get(u), v = get(v);
if(u == v) return;
// cout << u << ' ' << v << '\n';
// cout << sz[u] << ' ' << sz[v] << ' ' << w[make_pair(u, v)] << ' ' << w[make_pair(v, u)] << '\n';
ans += 2ll * sz[u] * sz[v] - 1ll * w[make_pair(u, v)] * sz[v] - 1ll * w[make_pair(v, u)] * sz[u];
w[make_pair(u, v)] = sz[u];
w[make_pair(v, u)] = sz[v];
if(p[u] != u) swap(u, v);
for(int child : children[v])
add_edge(child, u);
for(int child : children[u])
add_edge(child, v);
merge(u, v);
if(children[u].empty()) return;
set<int> st;
for(int child : children[u]) {
if(get(child) == u) continue;
st.insert(child);
}
children[u] = st;
}
void add_edge(int u, int v) {
u = get(u), v = get(v);
if(u == v) return;
if(w.count(make_pair(u, v))) return;
if(w.count(make_pair(v, u))) return void(combine(v, u));
ans += sz[v];
w[make_pair(u, v)]++;
if(w[make_pair(u, v)] == 1) children[v].insert(u);
}
};
MEGA_DSU d;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
d.init();
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
d.add_edge(u, v);
cout << d.ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
