finding bridges in graph in O(n+m)

bridges.cpp

// finding bridges in graph in O(n+m)
// https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=737

#include <bits/stdc++.h>
using namespace std;
int timer;

void dfs(int s,int par,vector<int>adj[],vector<bool>&vis,vector<int>&tin,vector<int>&low,vector<pair<int,int>>&ans){
    vis[s]=1;
    tin[s]=low[s]=++timer;
    for(auto u:adj[s]){
        if(u==par) continue;
        if(vis[u]){
            low[s]=min(low[s],tin[u]);
        }
        else{
            dfs(u,s,adj,vis,tin,low,ans);
            low[s]=min(low[s],low[u]);
            if(low[u]>tin[s]){
                ans.push_back({min(u,s),max(u,s)});
            }
        }
    }
}

int main() {
	int n;
	while(scanf("%d",&n)!=EOF){
	    vector<int>adj[n];
    	for(int i=0;i<n;i++){
    	    int s, m;
    	    scanf("%d (%d)",&s,&m);
    	   // cout<<s<<"-->";
    	    while(m--){
    	        int u;
    	        scanf("%d",&u);
    	       // cout<<u<<" ";
    	        adj[s].push_back(u);
    	    }
    	   // cout<<"\n\n";
    	}
    	timer=0;
    	vector<bool>vis(n,0);
    	vector<int>tin(n,0);
    	vector<int>low(n,0);
    	vector<pair<int,int>>ans;
    	for(int i=0;i<n;i++){
    	 if(!vis[i]) dfs(i,-1,adj,vis,tin,low,ans);   
    	}
    	cout<<ans.size()<<" "<<"critical links\n";
    	sort(ans.begin(),ans.end());
    	for(auto pi:ans){
    	    cout<<pi.first<<" - "<<pi.second<<"\n";
    	}
    	cout<<"\n";
	}
	return 0;
}

/*
Input format:
8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)

0

8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)

0
*/