Definition at line 11 of file bridge_finding_with_tarjan_algorithm.cpp.
◆ dfs() void Solution::dfs ( int current_node, int parent ) inlineprivateDefinition at line 17 of file bridge_finding_with_tarjan_algorithm.cpp.
17 {
18 visited.at(current_node) = true;
19 in_time[current_node] = out_time[current_node] = timer++;
20 for (auto& itr : graph[current_node]) {
21 if (itr == parent) {
22 continue;
23 }
24 if (!visited[itr]) {
25 dfs(itr, current_node);
26 if (out_time[itr] > in_time[current_node]) {
27 bridge.push_back({itr, current_node});
28 }
29 }
30 out_time[current_node] =
31 std::min(out_time[current_node], out_time[itr]);
32 }
33 }
◆ search_bridges() std::vector< std::vector< int > > Solution::search_bridges ( int n, const std::vector< std::vector< int > > & connections ) inlineDefinition at line 36 of file bridge_finding_with_tarjan_algorithm.cpp.
37 {
38 timer = 0;
39 graph.resize(n);
40 in_time.assign(n, 0);
41 visited.assign(n, false);
42 out_time.assign(n, 0);
43 for (auto& itr : connections) {
44 graph.at(itr[0]).push_back(itr[1]);
45 graph.at(itr[1]).push_back(itr[0]);
46 }
47 dfs(0, -1);
48 return bridge;
49 }
◆ bridge ◆ graph ◆ in_time ◆ out_time ◆ timer ◆ visitedThe documentation for this class was generated from the following file:
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4