我有一组边 E，我想知道是否可以安全地删除 E 中的边 i，这意味着如果我将其从图中删除，则该图仍应连接。
在我的理解中，这意味着边 i 必须位于一个圆上。输出应该是我无法删除的所有边的索引列表。
问题：
我的不同解决方案似乎做了正确的事情，但是太慢了（效率低下）。
我的解决方案之一是：
1. Loop through all edges i in E
2. Loop through all edges x in V
3. Add edge x to the graph (excluding edge i) until nodes of i are connected or end reached
4. If no connection possible, edge is not removable and added to the list
这种方式太慢了。
然后我决定重写我的代码并使用广度优先搜索来查看没有边缘 i 的另一条路径是否可行。
我认为它的性能足够好，但似乎不是。要么我以非常糟糕的方式实现，要么这也是该任务的错误算法。
这是我拥有的 C++ 代码中的算法（删除了一些不重要的部分）：
struct connection {
int a, b;
};
void expand(int x, connection *&arr, std::set<int> &exp, int size) {
for (int i = 0; i < size; i++) {
if (x == arr[i].a) {
exp.insert(arr[i].b);
}
else if (x == arr[i].b) {
exp.insert(arr[i].a);
}
}
return;
}
// recursive breadth-first-seach
bool BFSr(std::set<int> &group, std::set<int> &visited, int goal, connection *&arr, int size) {
if (group.empty()) return false;
if (group.find(goal) != group.end()) return true;
std::set<int> tempa;
for (std::set<int>::iterator it = group.begin(); it != group.end(); ++it) {
expand(*it, arr, tempa size);
}
for (std::set<int>::iterator it = visited.begin(); it != visited.end(); ++it) {
tempa.erase(*it);
}
tempb = visited;
tempb.insert(group.begin(), group.end());
return BFSr(tempa, tempb, goal, arr, size);
}
bool BFS(int start, int goal, connection *&arr, int size) {
std::set<int> tempa;
std::set<int> tempb;
tempa.insert(start);
return BFSr(tempa, tempb, goal, arr, size);
}
int main()
{
connection *arr = new connection[m];
connection *con = new connection[m - 1];
// fill arr with connections arr.a < arr.b ....
for (int j = 0; j < (m - 1); j++) {
con[j] = arr[j + 1];
}
// 1. edge for performance reasons extra
if (!BFS(arr[0].a, arr[0].b, con, (m - 1))) {
// connection is important therefore add to list
printf(" %d", 1);
}
// Look if nodes still connected after removing connection
for (int s = 1; s < m; s++) {
con[s - 1] = arr[s - 1];
if (!BFS(arr[s].a, arr[s].b, con, (m-1))) {
// connection is important therefore add to list
printf(" %d", s + 1);
}
}
printf("\n");
free(arr);
free(con);
return 0;
}
你知道我的任何解决方案可以让它更快吗，或者你知道我的问题有更好的算法吗？
