bridge in a graph
//Do watch striver graph series
#include<bits/stdc++.h>
using namespace std;
int timer=0;
void addedge(vector<int>adj[],int u,int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int node,int parent,vector<int>&visited,vector<int>&tim,vector<int>&low,vector<int>adj[])
{
visited[node]=1;
tim[node]=low[node]=timer++;
for(auto it:adj[node])
{
if(it==parent)
continue;
if(!visited[it])
{
dfs(it,node,visited,tim,low,adj);
low[node]=min(low[node],low[it]);
if(low[it]>tim[node])
{
cout<<node<<" "<<it<<endl;
}
}
else
{
low[node]=min(low[node],tim[it]);
}
}
}
int main()
{
int vertex,edges;
cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
cin>>vertex>>edges;
vector<int>adj[vertex];
int a,b;
cout<<"ENTER THE LINKS:"<<endl;
for(int i=0;i<edges;i++)
{
cin>>a>>b;
addedge(adj,a,b);
}
vector<int>timeinsertion(vertex,-1);
vector<int>lowtime(vertex,-1);
vector<int>visited(vertex,0);
for(int i=0;i<vertex;i++)
{
if(!visited[i])
{
dfs(i,-1,visited,timeinsertion,lowtime,adj);
}
}
return 0;
}