Collaboration diagram for Solution:

[legend]

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

Detailed Description

Definition at line 11 of file bridge_finding_with_tarjan_algorithm.cpp.

Member Function Documentation

◆ dfs()

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

inlineprivate

Definition at line 17 of file bridge_finding_with_tarjan_algorithm.cpp.

                                           {
        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

Definition at line 36 of file bridge_finding_with_tarjan_algorithm.cpp.

                                                             {
        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;
    }