c++ - 去除连通图中的边的算法

Question

问题:你有一个连接的，而不是有向图。有N个顶点。您还有一个结构数组:

struct Edge
{
     int a;
     int b;
}

数组 StructArray 表示所有的边。数组的大小为 M。找到最小的 k，使得从 StructArray 中删除所有边后，除了那些边:[0...k-1]，图仍然是连接的。

我的想法我不知道如何处理这个结构，所以我正在重建它(这可能是一个非常糟糕的方法)，以创建一个邻接列表:

vector < vector <int> > edges_list(N);

现在从 StructArray 的末尾开始，每次你想删除一条边时，你都在检查 edges_list:

edges_list[a].size() > 1 && edges_list[b].size() > 1;

您如何看待这个解决方案？好/坏？你还有别的吗？也许保留结构而不创建新结构？

Answer 1

我会逐步而不是递减地解决这个问题:从一个空图开始，一条一条地添加边，直到图连接起来。使用不相交集数据结构，如 Kruskal's algorithm检测何时只有一个连通分量。