删除k个顶点后的连通分量数

Question

我正在尝试解决以下图表问题：

We are given a general unweighted and undirected graph and k (k < |V| ) vertices that are already known beforehand. The vertices are deleted sequentially. After each deletion, how many connected components are there?

我想到了在每一步使用tarjan的算法来检查当前要删除的顶点是否是切割顶点，以便在执行删除时，我们可以简单地将邻居数添加到连通分量数。这个算法的复杂度是O(V(V+E)).

有人告诉我有一个 O(V+E) 算法可以执行此任务。但我想不通。对 Google 的研究也没有透露太多。谁能告诉我吗？

Answer 1

我们可以利用顶点事先已知的事实。

让我们解决一个"reverse"问题：给定一个图和一个按顺序添加到图中的顶点列表，计算每个添加结构后图中连通分量的数量。

解决方案非常简单：我们可以维护一个不相交的集合并集结构，并将与顶点关联的所有边添加到图中（很容易保持此结构中的组件数量：最初，它等于顶点数，并在联合实际发生时减一）。

原始问题通过以下方式简化为 "reverse" 问题：

让我们将不与任何已删除顶点关联的所有边添加到不相交集并集。
现在我们可以反转删除的顶点列表，并按照上述方法将它们一一添加。
之后，我们需要反转包含组件数量的结果列表。

注意：这个解实际上不是O(V + E)，而是O(V + E * alpha(V))，其中alpha(x)是反阿克曼函数。对于所有实际用途，它都非常接近线性。

Answer 2

这是我使用不相交集在 C++ 中实现的算法：

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef pair<int, int> pii;
const int M=2e5+137;

class DisjointSet {
    public:
    int connected_comp;
    int parent[100000];
    void makeSet(int n){
        for (int i=1;i<n+1; ++i)
            parent[i] = i;
        connected_comp = n; 
    }
    int Find(int l) {
        if (parent[l] == l) 
            return l;
        return Find(parent[l]);
    }
    void Union(int m, int n) {
        int x = Find(m);
        int y = Find(n);
        if(x==y) return;
        if(x<y){
            parent[y] = x;
            connected_comp--;
        }
        else{
            parent[x] = y;
            connected_comp--;
        }
    }

};

set<pii> not_delete;
vector<pii> to_add;

int main(){

    
    int node, edge;
    cout<<"enter number of nodes and edges"<<"\n";
    cin>>node>>edge;

    DisjointSet dis; 
    dis.makeSet(node); 
    cout<<"enter two nodes to add edges"<<"\n";
    for(int i=0;i<edge;i++){
        int u,v;
        cin>>u>>v;
        if(u>v){
            not_delete.insert({u,v});
        }
        else{
            not_delete.insert({v,u});
        }
    }

    int deletions;
    cout<<"enter number of deletions"<<"\n";
    cin>>deletions;
    cout<<"enter two node to delete edge between them"<<"\n";
    for(int i=0;i<deletions;i++){
        int u,v;
        cin>>u>>v;
        if(u>v){
            not_delete.erase({u,v});// edges that never delete from graph
            to_add.pb({u,v}); // edges that gonna delete from graph
        }
        else{
            not_delete.erase({v,u});
            to_add.pb({v,u});
        }
    }

    vector<int> res;
    

    // first adding edges that never delete from graph
    for(pii x: not_delete){
        dis.Union(x.first, x.second);
    }
    res.pb(dis.connected_comp);

    // then adding edges that will be deleted from graph backwards
    reverse(to_add.begin(), to_add.end());
    for(pii x: to_add){
        dis.Union(x.first, x.second);
        res.pb(dis.connected_comp);
    }
    cout<<"connected components after each deletion:"<<"\n";
    for (auto it =  ++res.rbegin(); it != res.rend(); ++it)
        cout << *it << "\n";


    return 0;
}

删除k个顶点后的连通分量数

Number of connected components after deleting k vertices

algorithm

graph

connected-components