Get the maximum sum of values of nodes among all connected components of an undirected graph
Problem Statement: You are given an undirected graph with connected components. Every node has a value assigned to it. You need to get the maximum sum of values of nodes among all connected components of an undirected graph. Example In the above example, there are 3 connected components and the sum of the nodes of […]
Find there is a path between 2 nodes in a directed graph
Problem Statement: You are given a directed graph and 2 nodes. You need to find if there is a path between those two nodes. Solution We use BSF to solve this problem. We take the first vertex as source and perform BSF operation on that vertex. If we get the second vertex, then there is […]
Given an directed graph, find the in and out degree of all vertices
Problem Statement: You are given an directed graph, you need to find out the in and out degree of all the vertiecs. Example Vertex In Out 0 0 3 1 1 2 2 2 1 3 3 0 Solution Solution is very simple. We need to traverse the adjacency list for all the vertices. The […]
Check if the undirected graph is a tree or not
Problem Statement: You are given a undirected graph. You need to see of that graph is a tree or not? Example Solution A graph can be a tree if if is connected and there are no loops. So we need to check for cycle for undirected graph and along with that we also mark the […]
Given a directed graph, check if the incoming edges of a vertex is equal to the vertex itself.
Problem Statement: You are given a directed graph, you need to check if the incoming edges of a vertex is equal to the vertex itself. Example The above graph should return true. Solution So the solution is to traverse the adjacency list for all the vertices. Then increment the count of edges of every vertex […]
Reverse a directed graph
Problem Statement: You are given an directed graph. You need to reverse the direction of the graph. Example Solution We will take another graph to hold the reverse of a graph. If there is a edge from v to u, then we add and edge from u to v in the reverse graph. Solution in […]
Count the number of connected components in an undirected graph
Problem Statement: You are given an undirected graph. YOu need to find out the number of connected componenets in taht graph. Example Output: 3 Solution We will use DFS to solve this problem. We will initialize a boolean array “visited”. Then for all the vertices we check if a vertex has been visited, if not […]
Check if undirected graph is connected or not
Problem Statement: You are given an undirected graph. You need to check if it is connected or not. Example Solution In the above image, the first graph is a connected graph, second is disconnected graph. In a connected graph, there is always a path from any node to any other node in the graph. We […]
Check if the given edge is a bridge in the graph
Problem Statement: You are given a graph and an edge, you need to check if that edge is a bridge. Example Solution An edge is called a bridge, if you remove that edge, then it will disconnect the graph. In the above example, the edge between the nodes “3” and “4” is a bridge. We […]
Strings: Longest Prefix Suffix
Problem Statement: You are given a string, you need to find the length of longest proper perfix which is also a suffix. Example Example 1: str = “abcdabc” Output: 3 Here “abc” is the longest prefix suffix Example 2: str = “abcdef Output: 3 Here there is no prefix that is also suffix Solution This […]