Я знаю, что алгоритм Тарьяна решает проблему нахождения мостов (ребер) в графе за линейное время. Я пытаюсь решить проблему немного по-другому. Я пытаюсь найти все ребра, которые являются частью цикла. Для этого я использую родительский массив, такой как parent[i]=j. Здесь j является родителем i, потому что вызов dfs(i) был сделан внутри / из dfs(j). Я также поддерживаю набор посещенных и посещающих узлов. Каждый раз, когда обнаруживается задний фронт, я просто пересекаю родительский массив, чтобы найти все ребра, принадлежащие этому циклу, и помещаю эти ребра в набор (скажем, cycle_edges). Теперь все ребра, которые не находятся внутри cycle_edges, являются мостами. Алгоритм показывает TLE в Leetcode OJ для больших входов. На первый взгляд, алгоритм выглядит линейным временем около 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;
}