c++ - Fast way to look if edge is important for graphs connectivity -

i have set of edges e, , want know if can safely remove edge in e, meaning if remove graph, graph should still connected.

in understanding implies edge i, has lie on circle. output should list of indices of edges can't remove.

the problem:

my different solutions seem right thing, far slow (inefficient).

one of solutions was:

1. loop through edges in e   2. loop through edges x in v     3. add edge x graph (excluding edge i) until nodes of connected or end reached   4. if no connection possible, edge not removable , added list 

this way way slow.

i decided rewrite code , use breadth-first-search if path possible without edge i.

i thought performant enough, seems it's not. either have implemented in bad way or that's wrong algorithm task.

here algorithm in c++ code have (removed not important parts):

struct connection {     int a, b; };  void expand(int x, connection *&arr, std::set<int> &exp, int size) {      (int = 0; < 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;      (std::set<int>::iterator = group.begin(); != group.end(); ++it) {         expand(*it, arr, tempa size);     }      (std::set<int>::iterator = visited.begin(); != 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 connections arr.a < arr.b ....      (int j = 0; j < (m - 1); j++) {         con[j] = arr[j + 1];     }      // 1. edge performance reasons     if (!bfs(arr[0].a, arr[0].b, con, (m - 1))) {         // connection important therefore add list         printf(" %d", 1);     }      // if nodes still connected after removing connection     (int s = 1; s < m; s++) {          con[s - 1] = arr[s - 1];          if (!bfs(arr[s].a, arr[s].b, con, (m-1))) {             // connection important therefore add list             printf(" %d", s + 1);         }     }      printf("\n");       free(arr);     free(con);      return 0; } 

do know solutions me make faster, or know better algorithm problem?

an edge deletion disconnects 2 connected components called bridge , there linear-time algorithms finding bridges in graph (usually based on depth-first search). wikipedia article lists 1 of them (due tarjan) example. this paper gives simple algorithm listing bridges in graph , seems bit simpler tarjan's algorithm.

hope helps!