Official

E - Graph Destruction Editorial by en_translator


As this problem is about connected components, we want to use Union-Find, but it allows us only to add an edge, but not to remove an edge.

Now, remember the common practice for query problems: “process queries in the reverse order.” So the problem can be rephrased as follows.

Add Vertices \(N,N-1,\ldots,1\) in this order.
When adding Vertex \(i\), add edges connecting \(i\) and \(j(j\gt i)\) to the graph at the same time.
How many connected components are there after adding Vertex \(i\)?

This can be found easily with Union-Find.
As for Union-Find, ACL (AtCoder Library) has a useful library named dsu. Please also refer to the sample code below.

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
typedef long long ll;

signed main(){
    ll n,m;cin>>n>>m;
    vector<vector<ll>>v(n+1);
    while(m--){
        ll a,b;cin>>a>>b;
        v[a].push_back(b);
    }
    dsu d(n+1);
    vector<ll>res={0}; // After removing all vertices through Vertex N, the answer is 0
    ll ans = 0; // Current number of connected components
    for(ll i=n;i>=2;i--){
        ans++; // Adds Vertex i
        for(auto j:v[i]){
            if(!d.same(i,j)){
                d.merge(i,j);
                ans--; // When vertices from different connected components are connected, the number of connected components decreases by 1
            }
        }
        res.push_back(ans);
    }
    reverse(res.begin(),res.end());
    for(auto x:res)cout<<x<<endl;
    return 0;
}

posted:
last update: