#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5+10;
set<int> adj[mxN], rev_adj[mxN], child[mxN];
int p[mxN];
ll ans = 0;
queue<pair<int, int>> to_merge;
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
void add(int a, int b) {
adj[a].insert(b);
rev_adj[b].insert(a);
if(adj[b].count(a)) {
to_merge.push({a, b});
}
}
int dsu_size(int a) {
return child[a].size() + adj[a].size() + rev_adj[a].size();
}
void uni(int a, int b) {
if(a == b) return ;
if(dsu_size(a) < dsu_size(b)) swap(a, b);
ans += (ll)(-p[b]) * child[a].size() + (ll)(-p[a]) * child[b].size();
p[a] += p[b];
p[b] = a;
for(auto it : child[b]) {
if(child[a].count(it)) ans += p[a];
else child[a].insert(it);
}
adj[a].erase(b), rev_adj[a].erase(b);
adj[b].erase(a), rev_adj[b].erase(a);
for(auto it : adj[b]) {
rev_adj[it].erase(b);
add(a, it);
}
for(auto it : rev_adj[b]) {
adj[it].erase(b);
add(it, a);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
p[i] = -1;
child[i].insert(i);
}
while(m--) {
int a, b;
cin >> a >> b;
b = get(b);
if(get(a) != b && !child[b].count(a)) {
child[b].insert(a);
ans += (ll)(-p[b]);
a = get(a);
add(a, b);
while(!to_merge.empty()) {
tie(a, b) = to_merge.front();
to_merge.pop();
uni(a, b);
}
}
cout << ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |