<p>An edge whose deletion disconnects two connected components is called a <strong><a href="http://en.wikipedia.org/wiki/Bridge_%28graph_theory%29" rel="nofollow">bridge</a></strong> and there are linear-time algorithms for finding all the bridges in a graph (usually based on depth-first search). The Wikipedia article lists one of them (due to Tarjan) as an example. <a href="http://arxiv.org/pdf/1209.0700.pdf" rel="nofollow">This paper</a> also gives a simple algorithm for listing all the bridges in a graph and seems to be a bit simpler than Tarjan's algorithm.</p>

<p>Hope this helps!</p>
Fast way to look if edge is important for graphs connectivity
<p>I have a set of edges E, and I want to know if I can safely remove edge i in E, meaning if I remove it from the graph, the graph should still be connected.</p>

<p>In my understanding that implies that edge i, has to lie on a circle.
The output should be a list of indices of all edges I can't remove.</p>

<p>The problem:</p>

<p>My different solutions seem to do the right thing, but are far too slow (inefficient).</p>

<p>One of my solutions was:</p>

<pre><code>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
</code></pre>

<p>This way was way too slow.</p>

<p>I then decided to rewrite my code and use breadth-first-search to look if another path is possible without edge i.</p>

<p>I thought it would be performant enough, but it seems it's not. Either I have implemented in a very bad way or that's also the wrong algorithm for this task.</p>

<p>Here is the algorithm in the C++ code I have (removed some not important parts):</p>

<pre><code>struct connection {
    int a, b;
};

void expand(int x, connection *&amp;arr, std::set&lt;int&gt; &amp;exp, int size) {

    for (int i = 0; i &lt; 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&lt;int&gt; &amp;group, std::set&lt;int&gt; &amp;visited, int goal, connection *&amp;arr, int size) {
    if (group.empty()) return false;
    if (group.find(goal) != group.end()) return true;
    std::set&lt;int&gt; tempa;

    for (std::set&lt;int&gt;::iterator it = group.begin(); it != group.end(); ++it) {
        expand(*it, arr, tempa size);
    }

    for (std::set&lt;int&gt;::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 *&amp;arr, int size) {
    std::set&lt;int&gt; tempa;
    std::set&lt;int&gt; 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 &lt; arr.b ....

    for (int j = 0; j &lt; (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 &lt; 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;
}
</code></pre>

<p>Do you know any solutions for me to make it faster, or do you know a better algorithm for my problem?</p>