Find Bridges in graph

Write a program to Find Bridges in the graph

Example 1:

Input: n=6,edges={{1,2},{2,3},{3,1},{4,3},{5,4},{6,4},{5,6}}
Output: 3-4 is a bridge , 1

Approach:

Java

import java.util.ArrayList;

public class FindBridgesInGraph {
    // visited array,in array,low array
    static ArrayList<Integer> visited = 
                new ArrayList<Integer>();
    static int in[];
    static int low[];

    // variable for dfs timer
    static int timer = 0;

    // variable for counter
    static int cnt = 0;

    public static void main(String[] args) {
        // adjacency list of the graph
        ArrayList<ArrayList<Integer>> adj = 
                    new ArrayList<>();

        int v = 7;
        // initialization of array
        in = new int[v];
        low = new int[v];
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 2, 3);
        addEdge(adj, 3, 1);
        addEdge(adj, 4, 3);
        addEdge(adj, 5, 4);
        addEdge(adj, 6, 4);
        addEdge(adj, 5, 6);
         // call dfs to find bridge
        dfs(adj, 1, -1);

    }

    private static void dfs(ArrayList<ArrayList<Integer>> adj,
                     int node, int parent) {
        visited.add(node);
        in[node] = timer;
        low[node] = timer;

        // increment the timer for next time
        timer++;

        // now interate for all adjacent nodes of the
        // current nodes
        for (int child : adj.get(node)) {
            // if child is same parent then continue
            if (child == parent)
                continue;
            // if alredy visited
            if (visited.indexOf(child) != -1) {
                // edge node-child is a back edge
                low[node] = Math.min(low[node], in[child]);
            } else {
                // edge node-child is a forward edge
                dfs(adj, child, node);
                if (low[child] > in[node]) {
                    cnt++;
                    System.out.println(node + " - " + child +
                             " is a bridge " + cnt);
                }
                low[node] = Math.min(low[child], low[node]);
            }
        }
    }

    // method to add edges into graph
    private static void addEdge(ArrayList<ArrayList<Integer>> g,
                         int u, int v) {
        // graph is undirected
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

C++

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

//adjacency list of the graph
vector<int> arr[10001];
//visited array,in array,low array
int visited[10001],in[10001],low[10001];

//varible for dfs timer
int timer;

//variable for counter
int cnt;

//function to add the edges into
//the graph
void addEdge(int u,int v)
{
    //graph is undirected
    arr[u].push_back(v);
    arr[v].push_back(u);
}
//dfs function
void dfs(int node,int par)
{
    //mark the current node as visited
    visited[node]=1;

    //in time and low time as current timer value
    in[node]=low[node]=timer;

    //increment the timer for next time
    timer++;

    //now interate for all adjacent nodes of the
    //current nodes
    for(int child:arr[node])
    {
      //if child is same parent then
      //continue
       if(child==par)
           continue;
      //if alredy visited
       if(visited[child]==1)
          {
              //edge node-child is a back edge
              low[node]=min(low[node],in[child]);
          }
        else
        {
         //edge node-child is a forward edge
         dfs(child,node);
         if(low[child]>in[node])
              {
                  cnt++;
                  cout<<node<<" - "<<child<<" is a bridge\n";
              }
            low[node]=min(low[child],low[node]);
        }
        
    }
}
int main()
{
    int n=6;
    addEdge(1,2);
    addEdge(2,3);
    addEdge(3,1);
    addEdge(4,3);
    addEdge(5,4);
    addEdge(6,4);
    addEdge(5,6);
    dfs(1,-1);
    cout<<"Number of brides are ";
    cout<<cnt<<"\n";
    return  0;
}