Rotten oranges problem

Rotten oranges problem goes like: In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens 4-directionally.

rotten oranges

Thoughts

Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.

On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.

This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:

Invalid grid return -1
Grid with all rotten oranges return 0
Grid with no rotten oranges and no fresh return 0
Grid with no rotten oranges and fresh present return -1
Grid post BFS with fresh oranges left return -1
Grid post BFS with all rotten oranges return count

Show me the implementation

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # Make sure we have a valid grid
        if len(grid) < 1 or len(grid[0]) < 1:
            return -1
        sources = []
        ones = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 2:
                    sources.append((i, j))
                elif grid[i][j] == 1:
                    ones += 1
        if len(sources) == 0:
            # In case of no rotten oranges, return value depending 
            # on the state of the grid
            if ones == 0:
                return 0
            else:
                return -1
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        # Grid is initially at t = -1
        count = -1
        visited = set(sources)
        # End the BFS when there are no new sources left
        while len(sources) > 0:
            count += 1
            newsources = []
            for source in sources:
                i, j = source
                grid[i][j] = 2
                for direction in directions:
                    row = i + direction[0]
                    col = j + direction[1]
                    # Make sure it is a valid row and column,
                    # It is not visited, and it is a fresh orange
                    if row >= 0 and row < len(grid) \
                       and col >= 0 and col < len(grid[0]) \
                       and (row, col) not in visited and grid[row][col] == 1:
                        newsources.append((row, col))
                        visited.add((row, col))
            sources = newsources
        # Make sure there are no fresh oranges left in the grid
        for i in grid:
            for j in i:
                if j == 1:
                    return -1
        return count

The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)

This article is contributed by Khushman Patel

Find friend groups

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. For example,

Input: 
[[1,1,0,0,0,0],
 [1,1,0,0,0,0],
 [0,0,1,1,0,0],
 [0,0,1,1,1,0],
 [0,0,0,1,1,0],
 [0,0,0,0,0,1]
]
Output: 3

Thought process

When we talk about the connections or relationships, we immediately will think of graph data structure. The node is the person and the edge is the relationship between two persons. So, first, we have to figure out whether it will be a directed graph or an undirected graph. In this problem, the friendship is a mutual relationship, thus the graph is undirected.

When you are reading this problem, the concept of Strongly Connected Components(SCC) will come into your mind. Ok, we will discuss why? If A is a friend of B, B is a friend of C, then A will be a friend of C. What does it mean? A is indirectly connected to C. It means that every friend can reach every other friend through a path if they are directly or indirectly connected. So in this way, they are forming a strong group or circle, in which every vertex is connected directly or indirectly in its group/circle. Notice that all friends (both direct and indirect), who should be in one friend circle are also in one connected component​ in the graph. 

A particular group of friends is a single component. In this problem we are going to find out how many components are there in the graph.

friend groups

When you make a graph out of it. It will be like this(see below fig). It means there are 3 friends circles.

friend-circle

We can solve this problem using 2 methods: depth first search and disjoint set method

Using Depth first traversal method

Finding connected components for an undirected graph is very easy. We can do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components

1. Initialize all nodes as not visited.
2. Initialize variable count as 1.
3. for every vertex 'v'.
       (i) If 'v' is unvisited
            Call DFS(v)
            count=count+1
DFS(v)
1. Mark 'v' as visited.
2. Do following for every unvisited neighbor `u`
      recursively call DFS(u)

DFS based approach implementation

class Solution {
Public:
    void DFS(int node,vector<vector<int>> edges,vecto<bool>visited)
    {
        int i;
        visited[node]=true;
        for(int i=0;i<edges[node].size();i++)
        {
            if(edges[node][i]==1 && node!=i && visited[i]==false)
            {
                DFS(i,edges,visited);
            }
        }
    }

    //Main Method
    int findCircleNum(vector<vector<int>> edges) {
        int i,j;
        
        int n=edges.size();
        int count=0;
        vector<bool>visited(m);
        
        //mark all the nodes as unvisited
        for(i=0;i<n;i++)
        {
            visited[i]=false;
        }
        
        for(i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                DFS(i,edges,visited);
                count=count+1;
            }
        }
        
        return count;
    }
};

Complexity

  • Time Complexity: Since we just go along the edges and visit every node, it will be O(n).
  • Space Complexity: O(n), to store the visited nodes.

Using Disjoint Sets(Union Find)

So, how to think that this problem is solved by Disjoint Sets(union-find algorithm)?

 The answer is simple because we need to keep track of the set of elements(here friends) partitioned into a number of non-overlapping subsets. Disjoint Sets(Union Find) always do this work very efficiently. We will use the Union by Rank algorithm to solve this problem.

If you haven’t heard of the Disjoint Sets. Go to this link and read about it.

To join two nodes, we will compare the rank of parents of both nodes.

  • If the rank is equal, we can make any one of the parent’s node as a parent and increment the rank of the parent node by 1.
  • If the rank is not same, then we can make the parent whose rank is greater than other.

graph breadth first traversal application

 

Let’s start solving this.

Union(1,2): 1 is a parent of itself and 2 is parent of itself. As both of them have different parents, so we have to connect them, and we will any of the parent as root, in this case we chose 1 and make it a parent.

friend groups

Union(2,1): 1 is a parent of itself and 1 is a parent of 2, as both of them have the same parents, already joined.

Union(3,4) :3 is a parent of itself and 4 is a parent of itself. Both of them have different parents, we need to join them.

Union(4,3): 3 is parent of itself and 3 is the parent of 4. Both of them have the same parents, already joined.

Union(4,5):   3 is the parent node of 4 and 5 is the parent node of 5. Since parents are different, we have to compare the rank of the parents of both 4 and 5 nodes. 3 has higher rank then 5, it will be parent of 5 .(Used Path Compression) as shown in the below fig.

Union(5,4): As now, 4 and 5 have the same parents, already joined. Last is the node 6 which connected to itself. So, nothing to do there. At the end of this exercise, we found that there are three different sets in the graph, and that is our answer of number of groups of friends in this graph or matrix.

Disjoint set based approach implementation

class Solution {
public:
    class Node
    {
        public:
            int data;
            Node*parent;
            int rank=0;
    };
    //make a set with only one element.
    void make(int data)
    {
        Node*node=new Node();
        node->data=data;
        node->parent=node;
        node->rank=0;
        mapy[data]=node;
        return;
    }
    map<int,Node*> mapy;
    //To return the address of the particular node having data as `data` 
    Node*find(int data)
    {
        auto k=mapy.find(data);
        if(k==mapy.end())
        {
            //There is no any node created, create the node
            make(data);
            return mapy[data];
        }
        else
        {
            return mapy[data];
        }
        return NULL;
    }
    /*Find the representative(parent) recursively and does path compression  
    as well*/
    Node*parents(Node*node)
    {
        if(node->parent==node)
        {
            return node;
        }
        return node->parent = parents(node->parent);
    }
    //Main Method
    int findCircleNum(vector<vector<int>>edges) {
        int i,j;
        
        vector<int> v;
        int m=edges.size();
        int n=edges[0].size();
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                if(edges[i][j]==1)
                {
                    int a=i;
                    int b=j;
                    
                    
                    Node*A=find(a);
                    Node*B=find(b);
            
                    Node*PA=parents(A);
                    Node*PB=parents(B);
            
                    if(PA==PB)
                    {
                    }
                    else
                    {
                        if(PA->rank>=PB->rank)
                        {
                            //increment rank if both sets have Same rank
                            PA->rank=(PA->rank==PB->rank)?PA->rank+1:PA->rank;
                            PB->parent=PA;
                        }
                        else
                        {
                            PA->parent=PB;
                        }
                    }
                    
                    }
                }
            }
        
        int number=0;
        for(auto k: mapy)
        {
            if(k.second->parent==k.second)
            {
                number=number+1;
            }
        }
        return number;
    }
};

Complexity

  • Time Complexity: For each of the edge, we need to find the parents  and do the union, which is O(mlogn).
  • Space Complexity: We used a map to store the parent information, O(n).

This post is contributed by Monika Bhasin

Tarjan’s Algorithm to find strongly connected components

Tarjan Algorithm is a very useful algorithm in finding strongly connected components in a directed graph. What is a strongly connected component?

What is Strongly Connected Component?

A directed graph is said to be strongly connected if we can reach any node from every other node in the graph. A strongly connected component of a directed graph is a subset of the nodes in the graph such that any two nodes of this subset are reachable from each other.
For any two nodes u and v in graph, if they are part of a strongly connected component, there exists a path from u to v and vice-a-versa.

For example, in the graph given below, there are 4 strongly connected components.
strongly connected components

There are two algorithms to strongly connected components one is Kosaraju’s algorithm and another one is the Tarjan algorithm.
Tarjan algorithm requires only one depth-first search traversal to find out all strongly connected components present in the graph. It is efficient as compared to Kosaraju’s algorithm as the other requires two DFS traversal.
An important thing to known to understand Tarjan’s algorithm is that depth-first traversal creates a DFS tree, meaning when we traverse a graph, it does traversal in a manner that a node is not visited again.

Tarjan’s algorithm to find Strongly Connected Component?

Fundamental is very simple: From a node u if we can reach to any of its ancestors for any of its descendants (including itself), then there must be a cycle containing this node, all these nodes should be part of the same connected component.

For example, if x is the root of the tree and y is the descendant of x and there is an edge from y to another node z that is an ancestor of x, then we can say that edge y – Z together with the paths in the DFS tree from z to x and from x to z form a cycle, which must all be part of the same component.

tarjan's algorithm

The edge from y to z is called back edge.

How can we know if there is a back-edge from a node to another? We keep track of two things for each node v of the graph:

tin[v]: Represents the number of node visited before v in DFS.
low[v]: Represents smallest tin[x] of a node reachable by a back edge from the subtree of v.

The below figure displays tin[i] for each node. In the simplest way, it can be calculated as in-time of the node in depth-first traversal.

strongly connected components in a graph

The interesting part is how to calculate low[i]? To start with, low[i] is the node the node i itself. Going forward, for each node u, go through its neighbors:
1. If the neighbor v not already visited, that means, it is not a back edge. We will go forward and do the DFS on the v. Once DFS is finished, we will update the low[u] as follows:

low[u] = min(low[u], low[v]).

2. If the node v is already visited, that means there is a back edge from node v to any of the ancestor of node u. In that case, low[u] will be defined as follows

low[u] = min(low[u], tin[v])

tarjan's algorithm to find strongly connected components

For node v, if tin[v] == low[v], v is then the root of the next connected component. If you want to print nodes in strongly connected components, keep track of them on the stack. As soon as we get a node with low[i] == tin[i], pop all the nodes from the stack till we get the node i. All of these nodes belong to same SCC.

If low[v] > tin[u], we can say that node u and v belong to different SCCs and edge (u,v) is a bridge edge.

Tarjan's algorithm to find strongly connected components

package AlgorithmsAndMe;

import java.util.*;

public class TarjansAlgorithm {

    Set<Integer> visited = new HashSet<>();
    /* This map stores the time when the
    current node is visited
     */
    int [] tin;
    /*
      low will store minimum on
       tin[v]
       tin[p] for all p for which (v,p) is a back edge
       low[to] for all to for which (v,to) is a tree edge
     */
    int [] low;

    //To maintain monotonic increasing order.
    int timer;

    void dfs(Graph g, int u, int parent, Stack<Integer> stack) {
        visited.add(u);

        //Put the current timer.
        tin[u] = timer;
        //Low is the time of entry to start with
        low[u] = timer;

        stack.push(u);
        timer++;

        /*
            Go through all the neighbors
         */
        for (int to : g.getNeighbors(u)) {
            //If it is parent, nothing to be done
            if (to == parent) continue;

            /* If the neighbor was already visited
                get the minimum of the neighbor entry time
                or the current low of the node.
             */
            if (visited.contains(to)) {
                low[u] = Math.min(low[u], tin[to]);
            } else {
                //Else do the DFS
                dfs(g, to, u,stack);
                /*
                 Normal edge scenario,
                 take the minimum of low of the parent and the child.
                 */
                low[u] = Math.min(low[u], low[to]);
            }
        }

        System.out.println();
        if (low[u] == tin[u]){
            //Print the stack.
            while(!stack.isEmpty() && stack.peek() != u){
                System.out.print(stack.pop() + " ");
            }
            System.out.print(u + " ");
            stack.pop();
        }
    }

    public void findConnectedComponents(Graph g) {
        timer = 0;
        Stack<Integer> stack = new Stack<>();
        Iterator it = g.getNodes().iterator();

        tin = new int[g.getSize() + 1];
        low = new int[g.getSize() + 1];
        Arrays.fill(tin, Integer.MAX_VALUE);
        Arrays.fill(low, Integer.MAX_VALUE);

        while(it.hasNext()){
            int i = (int) it.next();
            if (!visited.contains(i))
                dfs(g, i, -1, stack);
        }
    }
}

As we can see from the code that we only need one DFS traversal,therefore compexity of the algorithm will be O(|V| + |E|), where V and E are total number of vertex and edges present in the graph.

Problems solved using algorithm

1. Critical connection in a network.

Please write to us if you need coaching for your interview preparations.

Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
critical connection is a connection that, if removed, will make some server unable to reach some other server.
For example,
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
critical connections in a network

Before going through this solution, I would strongly recommend reading Tarjan’s algorithm and find bridges in a graph problem.

class Solution {
    int timer;

    List<List<Integer>> g;
      
    boolean [] visited;
    /* This map stores the time when the
    current node is visited
     */
    int [] tin;
    int [] low;
    
    void dfs(int u, int parent, 
                    List<List<Integer>> res ) {
        visited[u] = true;

        //Put the current timer.
        tin[u] = timer;
        //Low is the time of entry to start with
        low[u] = timer;

        timer++;

        /*
            Go through all the neighbors
         */
        for (int to : g.get(u)) {
            //If it is parent, nothing to be done
            if (to == parent) continue;

            /* If the neighbor was already visited
                get the minimum of the neighbor entry time
                or the current low of the node.
             */
            if (visited[to]) {
                low[u] = Math.min(low[u], tin[to]);
            } else {
                //Else do the DFS
                dfs(to, u, res);
                /*
                 Normal edge scenario,
                 take the minimum of low of the parent 
                  and the child.
                 */
                low[u] = Math.min(low[u], low[to]);

                /* If low of the child node is less than
                   time of entry of current node, then
                   there is a bridge.
                 */
                if (low[to] > tin[u]){
                   //List<Integer> l = new ArrayList<>();
                    List<Integer> l = 
                           Arrays.asList(new Integer[]{u, to});
                   res.add(l);
                }
            }
        }


    }

    public void findBridges(List<List<Integer>> res) {
        timer = 0;
        for(int i=0; i<g.size(); i++){
            if (!visited[i])
                dfs(i, -1, res);
        }
    }

  public List<List<Integer>> criticalConnections(int n, 
                             List<List<Integer>> connections) {
      

    g = new ArrayList<>(); 
      
    visited = new boolean[n];
    /* This map stores the time when the
    current node is visited
     */
    tin = new int[n];
    low = new int[n];
    
    Arrays.fill(visited, false);
    Arrays.fill(tin, n);
    Arrays.fill(low, n);
    
    for(int i=0; i<n; i++){
        g.add(new ArrayList<>());
    }
    for(List<Integer> l : connections){
          g.get(l.get(0)).add(l.get(1));  
          g.get(l.get(1)).add(l.get(0));   
      }
      
      List<List<Integer>> res = new ArrayList<>();
      findBridges(res);
    
      return res;
        
    }
}

The complexity of this code is O(V + E) where V is number of vertices and E is number of edges in the graph.

If you want help with interview preparations, please feel free to book a free demo session with us.

Matrix and graph traversals

Today, we will discuss an approach that can be used to solve quite a few problems with matrices. Problem structure is quite similar, you have a matrix, where cells represent real-world entities like land and water or oranges or walls and gates, etc. and we are asked to find something in that matrix. An example problem statement would be island problem. (taken from leetcode):

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

island problem graph dfs
In this example, there are three islands.

Most of the time these problems have two entities, in the above example, its water and land. At first sight, this problem does not give any hint that it is a graph problem. For a problem to be a graph problem, it must have nodes and edges.

What are the nodes and edges of the graph?

One hint is to the relationship between the cells of the matrix. For example, in the island problem, 0s are water, and 1s are land. Land can be connected to land only which is adjacent to the land and a piece of land is isolated if surrounded by water from all four sides.

In this case, nodes seem to be the cells with value 1(land). Most of the time, in these kinds of problems, each cell of the matrix with a certain value is a node. If we have an n x m matrix, we are looking at n x m possible nodes. Also, here be aware that we are not interested in all the cells. Based on the problem statement, we can discard some cells. For example, in the island problem, we are interested in the cells which represent the land.

Now, what will be the edges? In these kinds of problems, a statement is given like an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. It means that a cell with value 1 is connected to neighbor cells only if they also contain 1.

Now that we know that cells containing 1 in the matrix are nodes of the graphs and connected to neighbors in they are also 1. To count the number of islands, all we have to do is find connected components in the graph. We reduced a matrix problem to a graph problem after all. Should we create an entire graph? Well no, at any point in time, we do not need the entire graph.

Traversals of graphs like DFS or BFS need a node and its neighbors.

If we are at a particular cell of a matrix, we already know the node. With the problem definition, we can know which other cells can be a neighbor of this node. So, we do not need to actually convert the matrix to a graph but just mimic the getNeighbor(Node u) function of a graph.

Number of islands

The problem statement is given above as an example, we already identified the nodes and edges of the graph implicit in the matrix. We also know that to find the number of islands in the matrix, we have to find the number of connected components in the graphs as explained above. Which traversal can we use to find the number of connected components of a graph? It is a depth-first search problem.

  public int numIslands(char[][] grid) {
    int count = 0;
    Set<Integer> visited = new HashSet<>();

    int n = grid.length;
    
    if(n <=0) return 0;
    int m = grid[0].length;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int cell = i * m + j;
            if(!visited.contains(cell) && grid[i][j] == '1'){
                count++;
                dfs(i, j, visited, grid);
            }
        }
    }
    return count;
 }

void dfs(int i, int j, Set<Integer> visited, char[][] a){

    //Check if the node we are traversing is actually a valid node.
    if(i<0 || i>=a.length 
          || j<0 || j>=a[0].length 
          || a[i][j] == '0') return;

    int cell = i * a[0].length + j;
    if(visited.contains(cell)) return;
    visited.add(cell); 

    //Visit neighbors
    dfs(i+1, j, visited, a);
    dfs(i-1, j, visited, a);
    dfs(i, j+1, visited, a);
    dfs(i, j-1, visited, a);
}

Number of closed islands

There is another leetcode problem called Number of closed islands, it goes like:

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s. Return the number of closed islands.

Again, the similar structure of the problem, a matrix, cells representing the land and water. The only difference is now we have to find which land pieces are connected to the corners. Cells with 0s are lands, so cells with value 0 are our nodes. We will do a DFS starting from each of these nodes and see if we hit boundaries of the matrix, in that case, the node all these nodes cannot be closed islands.

  int numClosedIslands(int[][] g){
        int count = 0; 
        for(int i = 0;i < g.length;i++){
           for(int j = 0;j < g[0].length;j++){
                /* Our node is all the cells with 
                   value zero, we will do a DFS from each node
                */
                if(g[i][j] == 0){
                       count += dfs(g,i,j);
                }
           }
        }
        return count;
    }

    private int dfs(int[][] g,int row,int col){
         //if we meet the edge return 0;
         if(row < 0 || row >= g.length 
                || col < 0 || col >= g[0].length){
                 return 0;
         }
         //if we meet 1 return 1;
         if(g[row][col] == 1){
             return 1;
         }

         /* This is to make sure that 
             we do not visit same node again and again
         */
         g[row][col] = 1;

         /* Make sure that we do not reach to the boundaries 
         doing DFS. */
         int up = dfs(g,row-1,col);
         int down = dfs(g,row+1,col);
         int left = dfs(g,row,col-1);
         int right = dfs(g,row,col+1);

         //any of the sides meet the edge, is not an island;
         return up & down & left & right;
    }

Walls and gates problem

There is another problem which falls under the same criteria, the problem is known as walls and gates problem

Given a m x n 2D grid initialized with these three possible values. -1 – A wall or an obstacle. 0 – A gate. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

walls-and-gates

walls-and-gates-solution
Walls and gates solutions

In this problem, we have to find the distance to the room from gates and fill it with the minimum distance. Question number one, what are our nodes? In this problem, all the cells except the walls are nodes of the graph. Why walls are not nodes? Because one cannot go through the obstacles, so the cannot be part of the path of nodes, hence they cannot be considered as a node.

We can traverse horizontal and vertical, that means nodes at (i+1, j), (i-1, j), (i, j+1) and (i, j-1) are neighbors of cell (i,j) if they are a room or a gate.

To find the minimum distance from gates to a room, start a DFS from each gate and update the distance of the room with minimum distance seen so far. All we have to do it keep track of distance while starting from a gate.

package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class WallsAndGates {

    public int[][] wallsAndGates(int[][] grid){

        int n = grid.length;
        if(n<=0) return new int[0][0];

        int m = grid[0].length;

        Set<Integer> visited = new HashSet<>();

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                //This is our gate
                if(grid[i][j] == 0){
                    dfs(i, j, grid, 0, visited);
                }
            }
        }

        return grid;
    }

    private void dfs(int x, int y, int[][] grid,
                     int distance, Set<Integer> visited){

        int cellId = x*grid[0].length + y;
        if(x<0 || x>=grid.length
                || y<0 || y>grid[0].length
                || grid[x][y] == -1
                || visited.contains(cellId)){
            return;
        }

        //Mark as visited for this round.
        visited.add(cellId);

        //update the distance
        grid[x][y] = Math.min(grid[x][y], distance);

        dfs(x+1, y, grid, distance+1,visited);
        dfs(x-1, y, grid, distance+1, visited);
        dfs(x, y+1, grid, distance+1, visited);
        dfs(x, y-1, grid, distance+1, visited);

        //Mark unvisited for the next round.
        visited.remove(cellId);

    }
}

Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

In this problem, again all the cells with zero are nodes, and edges are between the horizontal and vertical neighbors nodes. To capture all the nodes which are not connected to the edge of the matrix, first, find out which all are actually connected to the edge and mark them. Once we know all the nodes which are connected to the edge of the matrix, we can capture the nodes which are not connected.
To do so, we will start with nodes at the edge of the matrix and find the connected component of it and mark all the nodes in that connected component.

 public void solve(char[][] grid) {
        int n = grid.length;
        if(n<=0) return;

        int m = grid[0].length;

        //Cover the first and last rows.
        for(int j=0; j<m; j++){
            if(grid[0][j] == 'O') dfs(0, j, grid);
            if(grid[n-1][j] == 'O') dfs(n-1, j, grid);
        }

        //Cover the first and last columns.
        for(int i=0; i<n; i++){
            if(grid[i][0] == 'O') dfs(i, 0, grid);
            if(grid[i][m-1] == 'O') dfs(i, m-1, grid);
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j] == 'O') grid[i][j] = 'X';
                if(grid[i][j] == '1') grid[i][j] = 'O';
            }
        }

        return;
    }

    private void dfs(int x, int y, char[][] grid){

        /* If we reach the edge of the node, return 
           Or we hit 'X', in that case, we cannot move
           further in that direction.
        */
        if(x<0 || x>=grid.length
                || y<0 || y>=grid[0].length
                || grid[x][y] == 'X'){
            return;
        }

        if(grid[x][y] == 'O') {
            grid[x][y] = '1';

            dfs(x + 1, y, grid);
            dfs(x - 1, y, grid);
            dfs(x, y + 1, grid);
            dfs(x, y - 1, grid);
        }
    }  
 

The time complexity of all the solutions mentioned above is O(n * m) where n and m are rows and columns of the matrix. Because we will visit each cell at least once.
Please share if there is something wrong or missing. If you are preparing for an interviews and need help with it, please book a free session with us.

Cycle in undirected graph using disjoint set

Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1.

detect cycle in undirected graph using disjoint set data structure

Disjoint-set data structure has two operations: union and find. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each edge(u,v) in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not?

detect cycle in undirected graph using disjoint set data structure

To start with, we initialize array A with the elements themselves.

detect cycle in a graph

Now, we process each node of the graph one by one. First is edge(1,2). The root of node(1) is 1 and the root of node(2) is 2. Since the roots of two vertices are different, we update the parent of the root of 2 which is A[2] to the root of 1 which is 1.

Next, we process edge(2,3), here root of the node(2) is 1, whereas the root node(3) is 3. Again they differ, hence update A[root of 3] with root 2, i.e A[3] = 1;

Now, process edge(2,4), it will end up with A[4] = 1, can you deduce why? And similarly edge(4,6) will also lead to update A[6] = 1.

detect cycle in directed graph using disjoint sets

Now, we process the edge(6,1). Here, root of node(6) is 1 and also the root of node(1) is 1. Both the nodes have same root, that means there is a cycle in the directed graph.

detect a cycle in undirected graph

To detect a cycle in direct graph : Implementation

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    private boolean isDirected;
    private int count;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        if(!this.G.containsKey(dest)) {
            this.G.put(dest, new ArrayList<>());
        }
        //In case graph is undirected
        if(!this.isDirected) {
                this.G.get(dest).add(start);
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }

    public boolean isCycleWithDisjointSet() {
        int[] parent = new int[this.G.size() + 1];

        for (int u = 1; u < this.G.size() + 1; u++) {
            //Process edge from each node.

            //Find root of u
            int i, j;

            //Worst complexity is O(V)
            for(i=u; i != parent[i]; i = parent[i]);

            /*This loop will run for O(E) times for all 
             the vertices combined. */
            for(int v: this.G.get(u)){
                for(j=v; j != parent[j]; j = parent[j]);

                if(i == j){
                    System.out.println("Cycle detected at 
                                        ("+ u + "," + v + ")");
                    return true;
                }

                parent[i] = j;
            }
        }
        return false;
    }
}

Test cases

package test.Graphs;

import com.company.Graphs.AdjacencyList;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyListTest {
    @Test
    public void detectCycleInDirectedGraphTest() {

        AdjacencyList tester = new AdjacencyList(false);

        tester.addEdge(1,5);
        tester.addEdge(3,4);
        tester.addEdge(2,4);
        tester.addEdge(1,3);
        tester.addEdge(3,5);
        tester.addEdge(5,2);

        assertEquals(true, tester.isEdge(3,4));
        assertEquals(false, tester.isEdge(1,4));

        assertEquals(true, tester.isCycleWithDisjointSet());

    }
}

Complexity of this algorithm is O(EV) where E is number of edges and V is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.

Disjoint set data structure

Disjoint set data structure

A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, ⋯ , 𝑆𝑛 } of disjoint dynamic sets. Subsets are said to be disjoint if intersection between them is NULL. For example, set {1,2,3} and {4,5,6} are disjoint sets, but {1,2,3} and {1,3,5} are not as intersection is {1,3} which is not null. Another important thing about the disjoint set is that every set is represented by a member of that set called as representative.

Operations on this disjoint set data structure:
1. Make Set: Creates a new set with one element x, since the sets are disjoint, we require that x not already be in any of the existing sets.
2. Union: Merges two sets containing x and y let’s say Sx and Sy and destroys the original sets.
3.Find: Returns the representative of the set which element belongs to.

Let’s take an example and see how disjointed sets can be used to find the connected components of an undirected graph.

To start with, we will make a set for each vertex by using make-set operation.

for each vertex v in G(V)
    do makeSet(v)

Next process all the edges in the graph (u,v) and connect set(u) and set(v) if the representatives of the set which contains u and set which contains v are not same.

for each edge (u,v) in 𝐺(E)
    do if findSet(u) != findSet(v)
        then union(u, v)

Once above preprocessing steps have run, then we can easily find answer if two vertices u and v are part of same connected component or not?

boolean isSameComponent(u, v)
 if findSet(u)==findSet(v)
     return True
 else 
     return False

To find how many components are there, we can look at how many disjoint sets are there and that will give us the number of connected components in a graph. Let’s take an example and see how it works.

disjoint set data structure

Below table shows the processing of each edge in the graph show figure above.

disjoint sets

Now, how can we implement sets and quickly do union and find operations? There are two ways to do it.

Disjoint set representation using an array

Simple implementation of disjoint set is using an array which maintains their representative of element i in A[i]. To this implementation to work, it is must that all the element in the set are in range 0 to N-1 where N is size of the array.

Initially, in makeSet() operation, set A[i]=i, for each i between 0 and N-1 and create the initial versions of the sets.

disjoint set data structure representation of graph

for (int i=0; i<N; i++) A[i] = i;

Union operation for the sets that contain integers u and v, we scan the array A and change all the elements
that have the value A[u] to have the value A[v]. For example, we if want to connect an edge between 1 and 2 in the above set, the union operation will replace A[2] with A[1].

disjoint set data structure time complexity and implementation in java

Now, if want to add an edge between 3 and 1. In this case, u = 3 and v = 1. A[3] = 3 and A[1] = 1. So, we will replace all the indices of A where A[i] = 1. So final array looks like this.

disjoint set data structure java

Similarly, if want to add an edge from 6 to 7.
disjoint sets

//change all elements from A[u] to A[v].
void union(int A[], int u, int v){
    int temp = A[u];
    for(int i=0; i<A.length; i++){
        if(A[i] == temp)
            A[i] = A[v]; 
    }
}

findSet(v) operation returns the value of A[v].

int findSet(int A[], int v){
    return A[v]
}

The complexity of makeSet() operation is O(n) as it initializes the entire array. Union operation take every time O(n) operations if we have to connect n nodes, then it will be O(n2) operations. FindSet() operation has constant time complexity.

We can represent a disjoint set using linked list too. In that case, each set will be a linked list, and head of the linked list will be the representative element. Each node contains two pointers, one to its next element it the set and other points to the representative of the set.

To initialize, each element will be added to a linked list. To union (u, v), we add the linked list which contains u to end of the linked list which contains v and change representation pointer of each node to point to the representation of list which contained v.

The complexity of union operation is again O(n). Also, find operation can be O(1) as it returns the representative of it.

Disjoint set forest

The disjoint-forests data structure is implemented by changing the interpretation of the meaning of the element of array A. Now each A[i] represents an element of a set and points to another element of that set. The root element points to itself. In short, A[i] now points to the parent of i.

Makeset operation does not change, as to start with each element will be the parent of itself.
Union operation will change, if we want to connect u and v with an edge, we update A[root of u] with the root of v. How to find the root of an element? As we have the relationship that A[i] is the parent of i, we can move up the chain until we find a case where A[i] == i, that case, i is the root of v.

//finding root of an element
int root(int A[],int i){
    while(A[i] != i){
        i = A[i];
    }
    return i;
}

/*Changed union function where we connect 
  the elements by changing the root of 
  one of the elements
*/

int union(int A[] ,int u ,int v){
    int rootU = root(A, u);       
    int rootV = root(A, v);  
    A[rootU] = rootV ; 
}

This implementation has a worst-case complexity of O(n) for union function. And also we made the worst complexity of findSet operation as O(n).

However, we can do some ranking on the size of trees which are being connected. We make sure that always root of smaller tree point to the root of the bigger tree.

void union(int[] A, int[] sz, u, v){

    //Finding roots
    for (int i = u; i != A[i]; i = A[i]) ;
    for (int j = v; j != A[j]; j = A[j]) ;

    if (i == j) return;
    //Comparing size of tree to put smaller tree root under 
    // bigger tree's root.
    if (sz[i] < sz[j]){
        A[i] = j;
        sz[j] += sz[i];
    }
    else {
        A[j] = i; 
        sz[i] += sz[j];
    }
}

In the next few posts, we will be discussing applications of this method to solve different problems on graphs.
Please share if there is something wrong or missing. If you are preparing for an interview, and want coaching sessions to prepare for it, please signup for free demo session.

Lowest common ancestor(LCA) using Range Minimum Query(RMQ)

Lowest common ancestor(LCA) using RMQ

We already have discussed lowest common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find the lowest common ancestor of two given nodes in a binary tree or binary search tree. LCA of two nodes u and v is the node which is furthest from root and u and v are descendant of that node. For example, LCA node(5) and node(9) in below tree is node(2).

lowest common ancestor using RMQ

In earlier solutions, we scan the whole binary tree every time we have to find LCA of two nodes. This has a complexity of O(n) for each query. If this query if fired frequently, this operation may become a bottleneck of the algorithm. One way to avoid processing all nodes on each query is to preprocess binary tree and store precalculated information to find LCA of any two nodes in constant time.

This pattern is very similar to a range minimum query algorithm. Can we reduce the lowest common ancestor problem to range minimum query problem?

Reduction of lowest common ancestor problem to RMQ

Let’s revise what is RMQ: Given an array A of length n; RMQ(i,j) – returns the index of the minimum element in the subarray A[i..j].

lowest common ancestor using RMQ

Let’s find LCA of two nodes 5 and 8 manually in the above binary tree. We notice that LCA(u,v) is a shallowest common node (in terms of distance from root) which is visited when u and v are visited using the depth-first search of the tree. An important thing to note is that we are interested in shallowest, which is minimum depth, the node between u and v. Sounds like RMQ?

Implementation wise, the tree is traversed as Euler tour, which means we visit each node of tree, without lifting the pencil. This is very similar to a preorder traversal of a tree. At most, there can be 2n-1 nodes in Euler tour of a tree with n nodes, store this tour in an array E[1..2n-1].

As algorithm requires the shallowest node, closest to root, so we store the depth of each node while doing Euler tour, so we store the depth of each node in another array D[1..2n-1].

We should maintain the value when the node was visited for the first time. Why?

E[1..2n-1] – Store the nodes visited in a Euler tour of T. Euler[i] stores ith node visited in the tour.
D[1..2n-1] – Stores level of the nodes in tour. D[i] is the level of node at Euler[i]. (level is defined to be the distance from the root).
F[1..n] – F[i] will hold value when node is first visited.

For example of this graph, we start from node(1) and do Euler tour of the binary tree.

lowest common ancestor using rmq

Euler tour would be like

lca using rmq

Depth array is like

lca using rmq

First visit array looks like

lca using rmq

To compute LCA(u,v): All nodes in the Euler tour between the first visits to u and v are E[F[u]...F[v]] (assume F[u] is less than F[v] else, swap u and v). The shallowest node in this tour is at index RMQ D(F[u]..F[v]), since D[i] stores the depth of node at E[i].
RMQ function will return the index of the shallowest node between u and v, thus output node will be E[RMQ D(F[u], F[v])] as LCA(u,v)

Let’s take an example, find the lowest common ancestor of node(5) and node(8).

First of all, find the first visit to node(5) and node(8). It will be F[5] which is 2 and F[8] which is 7.

Now, all the nodes which come between visit of node(5) and node(8) are in E[2..7], we have to find the shallowest node out these nodes. This can be done by applying RMQ on array D with range 3 to 6.

lca using rmq

LCA will be E[RMQ( D(2,7)], in this case, RMQ(D[2..7]) is index 3. E[3] = 2, hence LCA(5,8) is node(2).

Lowest common ancestor using RMQ: Implementation

package com.company.BST;

import java.util.Arrays;

/**
 * Created by sangar on 1.1.19.
 */
public class LowestCommonAncestor {

    private int[] E;
    private int[] D;
    private int[] F;

    int[][] M;

    private int tourCount;

    public LowestCommonAncestor(BinarySearchTree tree){
        //Create Euler tour, Depth array and First Visited array
        E = new int[2*tree.getSize()];
        D = new int[2*tree.getSize()];
        F = new int[tree.getSize() + 1];

        M = new int[2 * tree.getSize()][2 * tree.getSize()];

        Arrays.fill(F, -1);
        getEulerTour(tree.getRoot(), E, D, F, 0);

        preProcess(D);
    }

    public int findLowestCommonAncestor(int u, int v){
        //This means node is not in tree
        if(u >= F.length || v >= F.length || F[u] == -1 || F[u] == -1)
            return -1 ;

        return E[rmq(D, F[u], F[v])];
    }

    /* This function does all the preprocessing on the tree and
       creates all required arrays for the algorithm.
    */
    private void getEulerTour(TreeNode node, int[] E, int[] D, int[] F,
                              int level){
        if(node == null) return;

        int val = (int)node.getValue();

        E[tourCount] = val; // add to tour
        D[tourCount] =  level; // store depth

        if(F[val] == -1) {
            F[(int) node.getValue()] = tourCount;
        }
        tourCount++;
        
        if(node.getLeft() != null ) {
            getEulerTour(node.getLeft(), E, D, F, level + 1);

            E[tourCount] = val;
            D[tourCount++] = level;
        }
        if(node.getRight() != null ) {
            getEulerTour(node.getRight(), E, D, F, level + 1);

            E[tourCount] = val;
            D[tourCount++] = level;
        }
    }

    /*
      This function preprocess the depth array to quickly find 
      RMQ which is used to find shallowest node.
     */
    void preProcess(int[] D) {

        for (int i = 0; i < D.length; i++)
            M[i][0] = i;

        for (int j = 1; 1 << j <D.length ; j++){
            for (int i = 0; i + (1 << j) - 1 < D.length; i++){
                if (D[M[i][j - 1]] < D[M[i + (1 << (j - 1))][j - 1]])
                    M[i][j] = M[i][j - 1];
                else
                    M[i][j] = M[i + (1 << (j - 1))][j - 1];
            }
        }
    }

    private int rmq(int a[], int start, int end){
        int j = (int)Math.floor(Math.log(end-start+1));

        if ( a[ M[start][j] ] <= a[M[end-(1<<j)+1][j]] )
            return M[start][j];

        else
            return M[end-(1<<j)+1][j];
    }
}

The beauty of this algorithm is that it can be used to find LCA of any tree, not just only binary tree or BST. The complexity of the algorithm to find a lowest common ancestor using range minimum query is (O(n), O(1)) with an additional space complexity of O(n).

Reference
Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free demo class to guide you through the process.

Breadth First traversal

Breadth First traversal

In the last post, we discussed depth first traversal of a graph. Today, we will discuss another way to traverse a graph, which is breadth first traversal. What is breadth first traversal? Unlike depth-first traversal, where we go deep before visiting neighbors, in breadth-first search, we visit all the neighbors of a node before moving a level down. For example, breadth first traversal of the graph shown below will be [1,2,5,3,4,6]

breadth first traversal

In breadth first search, we finish visiting all the nodes at a level before going further down the graph. For example, the graph used in the above example can be divided into three levels as shown.

breadth first search

We start with a node in level 1 which is node(1). Then visit all the nodes which are one level below node(1) which are node(2) and node(5). Then we visit all the node at level 3 which are node(3), node(4) and node(6).

Breadth First Traversal: algorithm

  1. Start with the given node u, put node u to queue
  2. While queue is not empty, repeat below steps:
    1. Dequeue fro queue and print node u.
    2. For each neighbor of u, node v
    3. If v is not visited already: add v to the queue
    4. mark v as visited

Let’s take an example and see how it works. Below is the graph and we have to find BFS for this graph.
breadth first traversal

We start from node(1), and put it in the queue.
breadth first traversal of graph

While the queue is not empty, we should pop from it and print the node. In this case, node(1) will be printed. Next, we go through all the neighbors of node(1) and put all the unvisited node on the queue. node(2) and node(5) will go on to the queue and marked as visited. Traversal = {1}

breadth first search

Again, we dequeue from the queue and this time we get node(2). We print it and go for all the neighbor node, node(3) and node(4) and mark them as visited. Traversal = {1,2}

node(5) is dequeued next and printed. Here, even though node(4) is a neighbor of node(5), it is already visited and hence not put on to the queue again. But node(6) is not yet visited, so put it on to the queue. Traversal = {1,2,5}

Now, we pop node(3) and print it, however, node(4) is already visited. Hence, nothing is added to the queue. Traversal = {1,2,5,3}

Next, node(4) is taken out from queue and printed, nothing goes on to queue. Traversal = {1,2,5,3,4}

Last, we pop node(6) and print it. Traversal = {1,2,5,3,4,6}.

At this point, the queue is empty and we stop traversal.

Breadth first traversal: implementation

public ArrayList<Integer> breadthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();

        //This is start node
        q.add(1);
        visited[1] = true;

        while(!q.isEmpty()){
            int u = (int)q.remove();
            traversal.add(u);

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[u][i] && !visited[i]){
                    q.add(i);
                    visited[i]= true;
                }
            }
        }
        System.out.println(traversal);
        return traversal;

    }

The complexity of this code is O(V2) as at least V nodes will go in queue and for each nodes internal for loop runs V times.

Implementation of breadth-first search on graph represented by adjanceny list

  public ArrayList<Integer> breadthFirstTraversal(){

        boolean[] visited = new boolean[this.G.size()];
        ArrayList<Integer> traversal = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();

        //This is start node
        q.add(1);
        visited[1] = true;

        //This loop will run for V times, once for each node.
        while(!q.isEmpty()){
            int u = (int)q.remove();
            traversal.add(u);

            /*This loop has a worst-case complexity of O(V), where 
               node has an edge to every other node, but 
               the total number of times this loop will run is E times 
               where E number of edges.
             */
            for(int v : this.G.get(u)){
                if(!visited[v]){
                    q.add(v);
                    visited[v]= true;
                }
            }
        }
        System.out.println(traversal);
        return traversal;

    }

The complexity of Breadth First Search is O(V+E) where V is the number of vertices and E is the number of edges in the graph.

The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).

StackOverflow

When a graph is strongly connected, O(V + E) is actually O(V2)

Applications of Breadth first traversal

  1. To find shortest path between two nodes u and v
  2. To test bipartite-ness of a graph
  3. To find all nodes within one connected component

Please share if there is something wrong or missing. If you are preparing for an interview and want a free coaching session to guide you through it, please reach out to us at [email protected]

Find bridges in graph

Given a direct graph, detect bridges in the graph.

An edge is called as bridge edge if and only if on removal of that edge will increases number of components increase by one.

For example, in the below graphs, bridges are shown in green
bridges in graph

The concept of detecting bridges in a graph will be useful in solving the Euler path or tour problem.

Depth First Search of graph can be used to see if graph is connected or not. We can use the same concept, one by one remove each edge and see if the graph is still connected using DFS. If yes, then the edge is not bridge edge, if not, then edge is bridge edge.

However, this method entails quite a complexity of O(E * (V+E)) where E is number of edges and V is number of vertices.

Let’s think something better. Consider that we are looking at the edge (u,v) in a graph. In what condition, we can say that it is a bridge edge?
If we can somehow reach node u or any ancestor of u from any node which is a decedent of v, that means the graph is still connected and (u,v) is not a bridge edge. If the above condition is not possible, then (u,v) is the bridge.

How can we determine that there is no edge from decedent of v to u or its ancestor? For that we need to maintain time when a node was discovered during the depth-first search, call it tin[].

tin[u] is time when node u was discovered using DFS. If d[u] < d[v], means u was discovered before v.

Below is a graph with tin[u] filled for each node.
find bridges in a graph

Now, figure out the lowest tin[x] which can be reached from each node. Reason to find that is to see if there is a node x which is reachable from children of v and has tin[x] less than tin[u], i.e. x is ancestor of u reachable from children of v.

Store lowest DFS ancestor reachable from a node i in an array low[u].
low[u] = min(low[u], low[v])  for edge (u,v)

Idea here is that if (u,v) is an edge, then either there is no back edge from subtree of v to u and ancestor of u.
If there is a back edge to x from subtree of v, then minimum tin[x] reached by node in subtree will be assigned to the low[u].

The diagram shows the calculation of low[] in a graph.
bridge edges in a graph
Finally, if low[v] > tin[u] that means if discovery time of u is less than least ancestor that can be reached from subtree of v, we have a bridge, because there is no way we can reach to an ancestor of u once we disconnect edge (u,v).

Lots of theory, let’s code it. We will be modifying Depth First Search implementation to keep track of tin[] and low[].

Bridges in a graph implementation

package AlgorithmsAndMe;

import java.util.*;

public class Bridges {

    Set<Integer> visited = new HashSet<>();
    /* This map stores the time when the
    current node is visited
     */
    Map<Integer, Integer> tin = new HashMap<>();

    /*
      low will store minimum on 
       tin[v]
       tin[p] for all p for which (v,p) is a back edge
       low[to] for all to for which (v,to) is a tree edge
     */
    Map<Integer, Integer> low = new HashMap<>();
    
    //To maintain monotonic increasing order.
    int timer;

    void dfs(Graph g, int u, int parent) {
        visited.add(u);

        //Put the current timer.
        tin.put(u, timer);
        //Low is the time of entry to start with
        low.put(u,timer);
        
        timer++;
        
        /*
            Go through all the neighbors
         */
        for (int to : g.getNeighbors(u)) {
            //If it is parent, nothing to be done
            if (to == parent) continue;
            
            /* If the neighbor was already visited
                get the minimum of the neighbor entry time
                or the current low of the node.
             */
            if (visited.contains(to)) {
                low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
                        tin.getOrDefault(to, Integer.MAX_VALUE)));
            } else {
                //Else do the DFS
                dfs(g, to, u);
                /*
                 Normal edge scenario,
                 take the minimum of low of the parent and the child. 
                 */
                low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
                        low.getOrDefault(to, Integer.MAX_VALUE)));
                
                /* If low of the child node is less than
                   time of entry of current node, then
                   there is a bridge.
                 */
                if (low.get(to) > tin.get(u))
                    System.out.println(u + "->" + to);
            }
        }
    }

    public void findBridges(Graph g) {
        timer = 0;
        Iterator it = g.getNodes().iterator();
        while(it.hasNext()){
            int i = (int) it.next();
            if (!visited.contains(i))
                dfs(g, i, -1);
        }
    }
}

The complexity of finding bridges in a graph is O(V+E) where V is number of vertices and E is number of edges in graph.

Problems you can solve using this concept:
796 – Critical Links