bridge in a graph

Solutions on MaxInterview for bridge in a graph by the best coders in the world

showing results for - "bridge in a graph"
Leonardo
22 May 2019
1//Do watch striver graph series
2#include<bits/stdc++.h>
3using namespace std;
4 int timer=0;
5void addedge(vector<int>adj[],int u,int v)
6{
7    adj[u].push_back(v);
8    adj[v].push_back(u);
9}
10void dfs(int node,int parent,vector<int>&visited,vector<int>&tim,vector<int>&low,vector<int>adj[])
11{
12    visited[node]=1;
13    tim[node]=low[node]=timer++;
14    for(auto it:adj[node])
15    {
16        if(it==parent)
17            continue;
18        if(!visited[it])
19        {
20
21            dfs(it,node,visited,tim,low,adj);
22            low[node]=min(low[node],low[it]);
23
24            if(low[it]>tim[node])
25            {
26                cout<<node<<" "<<it<<endl;
27            }
28        }
29        else
30        {
31            low[node]=min(low[node],tim[it]);
32        }
33    }
34}
35int main()
36{
37    int vertex,edges;
38    cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
39    cin>>vertex>>edges;
40    vector<int>adj[vertex];
41    int a,b;
42    cout<<"ENTER THE LINKS:"<<endl;
43    for(int i=0;i<edges;i++)
44    {
45        cin>>a>>b;
46        addedge(adj,a,b);
47    }
48    vector<int>timeinsertion(vertex,-1);
49    vector<int>lowtime(vertex,-1);
50    vector<int>visited(vertex,0);
51    for(int i=0;i<vertex;i++)
52    {
53        if(!visited[i])
54        {
55            dfs(i,-1,visited,timeinsertion,lowtime,adj);
56        }
57    }
58    return 0;
59}
60