//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define maxn 100005
#define ll long long
using namespace std;
set<int> adj[maxn], rev[maxn];
int par[maxn];
ll siz[maxn], cnt[maxn];
ll ans = 0;
inline int find(int a) {
return a == par[a] ? a : par[a] = find(par[a]);
}
void Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
par[b] = a;
siz[a] += siz[b];
}
void combine(int a, int b) {
//cout << a << " " << b << endl;
if (find(a) == find(b)) return;
a = find(a), b = find(b);
if (adj[a].size() + rev[a].size() < adj[b].size() + rev[b].size()) swap(a, b);
//cout << a << " " << b << endl;
//cout << siz[a] << " " << cnt[b] - siz[a] << " " << siz[b] << " " << cnt[a] - siz[b] << endl;
ll oa = cnt[a], ob = cnt[b];
ans += 2 * siz[a] * siz[b] - siz[a] - siz[b];
vector<pair<int, int> > add;
for (int v:adj[b]) {
adj[a].insert(v);
rev[v].erase(b);
rev[v].insert(a);
if (rev[a].find(v) != rev[a].end()) {
add.push_back(make_pair(a, v));
}
}
for (int v:rev[b]) {
if (rev[a].find(v) == rev[a].end()) cnt[a] += siz[find(v)];
rev[a].insert(v);
adj[v].erase(b);
adj[v].insert(a);
if (adj[a].find(v) != adj[a].end()) {
add.push_back(make_pair(a, v));
}
}
//cnt[a] = rev[a].size();
//cout << cnt[a] - ob << " " << siz[b] << " " << cnt[a] - oa << " " << siz[a] << endl;
ans += (cnt[a] - ob) * siz[b] + (cnt[a] - oa) * siz[a];
Union(a, b);
for (auto v:add) {
combine(v.first, v.second);
}
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) {
par[i] = i, siz[i] = 1;
}
for (int i = 0;i < m;i++) {
int a, b;
cin >> a >> b;
a = find(a), b = find(b);
if (a == b || adj[a].find(b) != adj[a].end()) {
cout << ans << "\n";
continue;
}
adj[a].insert(b);
rev[b].insert(a);
cnt[b] += siz[a];
ans += siz[b];
if (adj[b].find(a) != adj[b].end()) {
combine(a, b);
}
cout << ans << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
9708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
