#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
long long ans;
int p[N];
vector<int> cl[N];
set<int> in[N], in2[N];
long long tot(int v) {
return 1ll * cl[v].size() * (cl[v].size() - 1);
}
int get(int v) {
return (v == p[v] ? v : p[v] = get(p[v]));
}
long long kek(int v) {
return 1ll * cl[v].size() * in[v].size();
}
void unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) {
return;
}
if (cl[u].size() + in[u].size() < cl[v].size() + in[v].size()) {
swap(u, v);
}
ans -= tot(u);
ans -= tot(v);
ans -= kek(v);
ans -= kek(u);
for (int x : cl[v]) {
cl[u].push_back(x);
if (in[u].count(x)) {
in[u].erase(x);
}
}
for (int x : in[v]) {
if (get(x) != u) {
in[u].insert(x);
}
}
for (int x : in2[v]) {
if (x != u) {
in2[u].insert(x);
}
}
ans += kek(u);
ans += tot(u);
p[v] = u;
}
void connect(int u, int v) {
if (get(u) == get(v)) {
return;
}
if (in[get(v)].count(u)) {
return;
}
if (in2[get(u)].count(get(v))) {
unite(u, v);
} else {
ans += cl[get(v)].size();
in[get(v)].insert(u);
in2[get(v)].insert(get(u));
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cl[i].push_back(i);
p[i] = i;
}
while (m--) {
int u, v;
cin >> u >> v;
--u, --v;
connect(u, v);
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
