#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
int n;
vector<int> p;
vector<int> sz;
DSU(int n = 0): n(n), p(n+1), sz(n+1,1) { iota(p.begin(), p.end(), 0); }
int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
// merge b into a (caller ensures a != b and a is new root)
void set_parent(int b, int a){
p[b] = a;
sz[a] += sz[b];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if(!(cin >> N >> M)) return 0;
DSU dsu(N);
// node-level outgoing edges for mutual detection
vector<unordered_set<int>> g(N+1);
for(int i=1;i<=N;i++) g[i].reserve(1);
// component-level adjacency sets (store roots)
vector<unordered_set<int>> out(N+1), in(N+1);
for(int i=1;i<=N;i++){
out[i].reserve(1);
in[i].reserve(1);
}
// sizes available from dsu.sz
// answer maintained as:
// ans = sum over comps size[c]*(size[c]-1) + sum over directed comp edges a->b of size[a]*size[b]
ll ans = 0;
auto safe_find = [&](int x){ return dsu.find(x); };
// helper to add an inter-component directed edge ra -> rb (roots)
auto add_comp_edge = [&](int ra, int rb){
if(ra == rb) return;
// insert if not exists
if(out[ra].insert(rb).second){
in[rb].insert(ra);
ans += 1LL * dsu.sz[ra] * dsu.sz[rb];
}
};
// unite components a and b (by node indices). We'll merge smaller into larger.
function<void(int,int)> unite = [&](int u, int v){
int a = dsu.find(u), b = dsu.find(v);
if(a == b) return;
// ensure a is larger
if(dsu.sz[a] < dsu.sz[b]) swap(a,b);
// subtract old internal contributions
ans -= 1LL * dsu.sz[a] * (dsu.sz[a] - 1);
ans -= 1LL * dsu.sz[b] * (dsu.sz[b] - 1);
// move out-edges of b
// iterate over a snapshot to allow safe modification
vector<int> tmp_out;
tmp_out.reserve(out[b].size());
for(int t : out[b]) tmp_out.push_back(t);
for(int t0 : tmp_out){
int t = dsu.find(t0);
// remove b from in[t]
auto it_in = in[t].find(b);
if(it_in != in[t].end()) in[t].erase(it_in);
if(t == a){
// previously contributed sz[b]*sz[a], now internal -> remove that contribution
ans -= 1LL * dsu.sz[b] * dsu.sz[a];
// do not add any out-edge
} else {
// if a already has edge to t -> no net change in cross-sum
if(out[a].find(t) == out[a].end()){
// create new edge a->t
out[a].insert(t);
in[t].insert(a);
// previously contribution was sz[b]*sz[t]; now it's (sz[a]+sz[b])*sz[t]
// increase by sz[a]*sz[t]
ans += 1LL * dsu.sz[a] * dsu.sz[t];
} else {
// a already had edge to t; previous contributions (sz[a]*sz[t] + sz[b]*sz[t]) remain equal to (sz[a]+sz[b])*sz[t]
// no change needed
}
}
// erase entry from out[b] (we will clear afterwards)
}
out[b].clear();
// move in-edges of b
vector<int> tmp_in;
tmp_in.reserve(in[b].size());
for(int s : in[b]) tmp_in.push_back(s);
for(int s0 : tmp_in){
int s = dsu.find(s0);
// remove b from out[s]
auto it_outs = out[s].find(b);
if(it_outs != out[s].end()) out[s].erase(it_outs);
if(s == a){
// previously contributed sz[a]*sz[b], now internal -> remove that contribution
ans -= 1LL * dsu.sz[a] * dsu.sz[b];
} else {
// if s already has edge to a -> no net change
if(out[s].find(a) == out[s].end()){
out[s].insert(a);
in[a].insert(s);
// previously contribution sz[s]*sz[b], now becomes sz[s]* (sz[a]+sz[b]) so increase by sz[s]*sz[a]
ans += 1LL * dsu.sz[s] * dsu.sz[a];
} else {
// already had edge s->a, no change
}
}
// erase entry from in[b] (we will clear afterwards)
}
in[b].clear();
// set parent and update size
dsu.set_parent(b, a);
// add new internal contribution
ans += 1LL * dsu.sz[a] * (dsu.sz[a] - 1);
};
for(int i=0;i<M;i++){
int A,B; cin >> A >> B;
// add node-level edge A -> B
g[A].insert(B);
int ra = safe_find(A), rb = safe_find(B);
// add component-level directed edge if inter-component
if(ra != rb){
add_comp_edge(ra, rb);
}
// if mutual, unite components of A and B
if(g[B].find(A) != g[B].end()){
unite(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... |