#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int sz[N];
int p[N];
set <int> out[N];
set <int> in[N];
set <int> who[N];
set <int> ver[N];
int get(int a) {
return (a == p[a] ? a : p[a] = get(p[a]));
}
ll ans = 0;
void join(int a, int b) {
a = get(a);
b = get(b);
if (a != b) {
ans -= (ll)sz[a] * (sz[a] - 1);
ans -= (ll)sz[b] * (sz[b] - 1);
if (in[a].size() + out[a].size() + who[a].size() + ver[a].size() > in[b].size() + out[b].size() + who[b].size() + ver[b].size()) swap(a, b);
in[a].erase(b);
out[a].erase(b);
in[b].erase(a);
out[b].erase(a);
ans += (ll)who[a].size() * sz[b];
ans += (ll)who[b].size() * sz[a];
for (int x : who[a]) {
if (who[b].count(x)) {
ans -= sz[a] + sz[b];
} else if (ver[b].count(x)) {
ans -= sz[a] + sz[b];
} else {
who[b].insert(x);
}
}
for (int x : ver[a]) {
if (who[b].count(x)) {
ans -= sz[a] + sz[b];
who[b].erase(x);
}
ver[b].insert(x);
}
vector <pair <int, int>> to_join;
for (int x : in[a]) {
if (out[b].count(x)) {
to_join.push_back({x, b});
}
in[b].insert(x);
out[x].erase(a);
out[x].insert(b);
}
for (int x : out[a]) {
if (in[b].count(x)) {
to_join.push_back({x, b});
}
out[b].insert(x);
in[x].erase(a);
in[x].insert(b);
}
who[a] = {};
ver[a] = {};
in[a] = {};
out[a] = {};
p[a] = b;
sz[b] += sz[a];
ans += (ll)sz[b] * (sz[b] - 1);
for (auto p : to_join) join(p.first, p.second);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
p[i] = i;
sz[i] = 1;
ver[i].insert(i);
}
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
int a = get(u);
int b = get(v);
if (a != b) {
out[a].insert(b);
in[b].insert(a);
}
if (!who[b].count(u)) {
who[b].insert(u);
ans += sz[b];
}
if (out[b].count(a)) {
join(a, b);
}
cout << ans << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
