#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN = 100000;
int n, m, p[mxN], sz[mxN];
ll ans = 0;
set<pair<int, int>> seen;
set<int> s[mxN];
int find(int i) {
return i == p[i] ? i : p[i] = find(p[i]);
}
void merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
ans -= (ll)sz[a] * (sz[a] - 1);
ans -= (ll)sz[b] * (sz[b] - 1);
ans -= (ll)s[a].size() * sz[a];
ans -= (ll)s[b].size() * sz[b];
// now merge them
p[b] = a;
sz[a] += sz[b];
if (s[a].size() < s[b].size()) swap(s[a], s[b]);
for (const int& i : s[b]) s[a].insert(i);
for (auto it = s[a].begin(); it != s[a].end();) {
if (find(*it) == a) it = s[a].erase(it);
else ++it;
}
ans += (ll)sz[a] * (sz[a] - 1);
ans += (ll)s[a].size() * sz[a];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
fill(sz, sz + n, 1);
iota(p, p + n, 0);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b, --a, --b;
if (seen.count({b, a})) {
merge(a, b);
}
else {
seen.emplace(a, b);
b = find(b);
if (!s[b].count(a)) {
ans += sz[b];
s[find(b)].insert(a);
}
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
