GENTHRU - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest
Practice

Author: vallabh43

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graphs

PROBLEM:

Given a connected graph calculate the number of edges which when removed disconnects the path between at least one pair of nodes.

QUICK EXPLANATION:

The required edges must separate the graph into 2 or more connected components. Thus, we have to find the number of bridges in a graph.

EXPLANATION:

We consider the cities on greed island as nodes and roads between them as edges of a graph.
Genthru wants to destroy a road that results in there being no route between at least 1 pair of cities, which means we must find the number of edges that when removed, disconneecxt the graph These edges are known as bridges.

To calculate the number of bridges, we make use of the fact that an edge (u, v) is a bridge if and only if, in its DFS traversal tree, neither v nor its descendant has any back edge to u or any of its ancestors.

You can read more about finding bridges here.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>

using namespace std;

int n, m, bridges;
vector< vector< int > > adj;

vector< short > visited;
vector< int > tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    for (int to : adj[v]) {
        if (to == p) continue;
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v])
                ++bridges;
        }
    }
}

void find_bridges(){
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        bridges = 0;
        cin>>n>>m;
        adj = vector< vector< int > > (n);
        while(m--){
            int a, b;
            cin>>a>>b;
            --a, --b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        find_bridges();
        cout<<bridges<<"\n";
    }
    return 0;
}

Time Complexity: O(t*(n+m))

2 Likes