在无向图中找到关键连接（桥）。我的进场时间不是线性时间吗？

Question

我知道Tarjan算法解决了在线性时间内查找图形中的桥（切边）的问题。我试图以稍微不同的方式解决问题。我尝试找到所有属于循环的边缘。为此，我使用了一个父数组，例如parent[i]=j。这里j是i的父级，因为对dfs(i)的调用是在dfs(j)内部进行的。我还维护了一组访问和访问节点。每次找到后沿时，我都会遍历父数组以查找属于该循环的所有边，并将这些边转储到集合中（例如cycle_edges）。现在，不在cycle_edges内的所有边都是桥。对于大输入，该算法在Leetcode OJ中显示TLE。从表面上看，该算法看起来线性时间大约为O(V+nE)。是否如果我的图形中有太多的循环，并且某些边属于多个循环，我每次都使用父数组进行遍历，从而增加n并使其过高？您可以在下面找到我的dfs函数的代码片段。如果有人可以帮助我解决这个特定解决方案的时间问题，我将非常感激。谢谢！

    void dfs(vector<vector<int>>& graph, int current_node, vector<int>& parent, unordered_set<int>& visiting, unordered_set<int>& visited, unordered_set<pair<int, int>, PairHash>& cycle_edges){

        visiting.insert(current_node);
        //cout << "Current node: " << current_node << endl; 
        for (auto neighbor: graph[current_node])
        {
          if (visiting.find(neighbor) == visiting.end() && visited.find(neighbor) == visited.end()){
            parent[neighbor] = current_node;
            dfs(graph, neighbor, parent, visiting, visited, cycle_edges);
          }
          else if(visiting.find(neighbor) != visiting.end() && visited.find(neighbor) == visited.end()){
            if (parent[current_node] != neighbor){
              //found a back edge
              //cout << "Found a back edge" << endl;
              if (neighbor > current_node){
                cycle_edges.insert({current_node, neighbor});
                //cout << current_node << " " << neighbor << endl;
              }
              else{
                cycle_edges.insert({neighbor, current_node});
                //cout << neighbor << " " << current_node << endl;
              }

              int node_first = current_node;
              int node_second = parent[current_node];

              while (node_first != neighbor){
                if (node_first > node_second){
                  cycle_edges.insert({node_second, node_first});
                  //cout << node_second << " " << node_first << endl;
                }
                else{
                  cycle_edges.insert({node_first, node_second});
                  //cout << node_first << " " << node_second << endl;
                }
                node_first = node_second;
                node_second = parent[node_second];
              }
            }
          }
        }
        visiting.erase(current_node);
        visited.insert(current_node);
        return;
    }

Answer 1

该代码在O（V + E）中有效，但是可以进行一些小的优化。

vector<int> visiting(n,0),visited(n,0);可以代替集合来跟踪访问和被访问节点的记录。

[unordered_set<>]后面具有散列功能，通常包含较大的恒定时间复杂度。

使用vector<set<int>>(n,unordered_set<int>())可能更好。

如果查询每个边以查找其是否存在于cycle_edges中，则需要花费|E| * find_complexity时间。

您可以将每个边分成一个较低编号的顶点，该顶点将指向我们要搜索其较高编号的邻居的集合。

如果您可以提供问题的链接，也许可以找到更好的方法。