Solution Class Reference

Collaboration diagram for Solution:

Public Member Functions
std::vector< std::vector< int > >	search_bridges (int n, const std::vector< std::vector< int > > &connections)

Private Member Functions
void	dfs (int current_node, int parent)

Private Attributes
std::vector< std::vector< int > >	graph
std::vector< int >	in_time
std::vector< int >	out_time
int	timer = 0
std::vector< std::vector< int > >	bridge
std::vector< bool >	visited

Member Function Documentation

dfs()

void Solution::dfs ( int current_node, int parent )

inlineprivate

                                           {
        visited.at(current_node) = true;
        in_time[current_node] = out_time[current_node] = timer++;
        for (auto& itr : graph[current_node]) {
            if (itr == parent) {
                continue;
            }
            if (!visited[itr]) {
                dfs(itr, current_node);
                if (out_time[itr] > in_time[current_node]) {
                    bridge.push_back({itr, current_node});
                }
            }
            out_time[current_node] =
                std::min(out_time[current_node], out_time[itr]);
        }
    }

search_bridges()

std::vector< std::vector< int > > Solution::search_bridges ( int n, const std::vector< std::vector< int > > & connections )

inline

                                                             {
        timer = 0;
        graph.resize(n);
        in_time.assign(n, 0);
        visited.assign(n, false);
        out_time.assign(n, 0);
        for (auto& itr : connections) {
            graph.at(itr[0]).push_back(itr[1]);
            graph.at(itr[1]).push_back(itr[0]);
        }
        dfs(0, -1);
        return bridge;
    }

---

The documentation for this class was generated from the following file:

• graph/bridge_finding_with_tarjan_algorithm.cpp