#include <bits/stdc++.h>
#define ll int
#define ld long double
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = INT_MAX;
struct DSU{
struct Vertex{
set<ll> in, out, foll;
ll sz;
ll size(){
return foll.size();
}
};
ll cnt, sz;
vector<Vertex> a;
queue<pair<ll, ll>> unity;
vector<ll> p;
DSU(ll N){
a.resize(N+1);
sz=N;
for (ll i=1; i<=sz; i++){
a[i].sz=1;
a[i].foll.insert(i);
}
p.resize(N+1, -1);
cnt=0;
}
ll get(ll x){
return p[x]==-1?x:p[x]=get(p[x]);
}
void merge(ll pu, ll pv){
a[pv].in.insert(pu);
a[pu].out.insert(pv);
if (a[pu].in.count(pv)){
unity.push({pu, pv});
}
}
void unite(ll u, ll v){
u = get(u); v = get(v);
if (u==v) return;
if (a[u].size()<a[v].size()){
swap(u, v);
}
// cout << u << "-" << v << " -- " << cnt << ln;
cnt+=a[u].sz*a[v].foll.size()+a[v].sz*a[u].foll.size();
// cout << cnt << ln;
for (auto fol:a[v].foll){
if (a[u].foll.count(fol)) cnt-=a[u].sz+a[v].sz;
else{
a[u].foll.insert(fol);
}
}
// cout << cnt << ln;
a[u].in.erase(v);
a[u].out.erase(v);
a[v].in.erase(u);
a[v].out.erase(u);
p[v]=u;
a[u].sz+=a[v].sz;
for (auto out:a[v].out){
a[out].in.erase(v);
merge(v, out);
}
for (auto ind:a[v].in){
a[ind].out.erase(v);
merge(ind, u);
}
}
void link(ll u, ll v){
ll pu = get(u), pv = get(v);
if (pu!=pv and !a[pv].in.count(u)){
a[pv].foll.insert(u);
cnt+=a[pv].sz;
// cout << u << "-" << v << ":" << cnt << ln;
merge(pu, pv);
while (!unity.empty()){
unite(unity.front().ff, unity.front().ss);
unity.pop();
}
}
}
};
void solve(){
ll n, m; cin >> n >> m;
DSU tree(n);
while (m--){
ll u, v; cin >> u >> v;
tree.link(u, v);
cout << tree.cnt << endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
