Last Updated: 15 Feb, 2021

Minimum Weight In A Connected Component

Moderate

Asked in company

Solve now

Problem statement

You are given a directed graph of several connected components (maybe only one). Every node of the graph has at most one outgoing edge and at most one incoming edge. The graph does not contain any cycles or self-loops.

There is a weight associated with each edge of the graph. Your task is to find out the number of connected components, the starting and ending node of each component, and the minimum weight in that component. It is guaranteed that each component has at least one edge.

For Example :

The example of a graph is shown in the below figure.

graph_example

So, there are two connected components in the above graph. The starting and ending node of one component is 1 and 3, respectively, and the minimum weight in this component is 9. The starting and ending node in the other component is 4 and 5 respectively, and the minimum weight is 11.

Input format :

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains two space-separated integers N and M, denoting the number of nodes and the number of edges in the graph, respectively.

Then M lines follow. Each line contains three space-separated integers denoting the source, destination, and weight of each edge.

Output format :

For each test case, print the number of connected components. Let’s denote this as C. Then C lines follow. 

Each line contains three space-separated integers representing each component’s starting and ending node and the minimum weight in that component.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N, M <= 5000
1 <= Source and Destination of an edge <= N 
1 <= weight of an edge <= 10^5

Time limit: 1 second

Solve now

Approaches

01 Approach

The idea here is to traverse each node of the graph. If a node doesn’t have an incoming edge but has an outgoing edge, then we should start a Depth First Search from this node passing another variable by reference to store the minimum weight in this component. We return the last node of the component from this function.

Steps:

Create three arrays named to start, end, and weights to store the graph. Each array should be of size N + 1.
Run a loop i = 0 to M and do:
- Let’s denote edges[i][0] as src, edges[i][1] as dest and edges[i][2] as weight.
- Make start[src] = dest, weights[src] = weight and end[dest] = src.
Create an array/list to store the result, i.e., the starting and ending of each component along with the minimum weight in each component. Let this array be res.
Run a loop from i = 1 to N and do:
- If end[i] == 0 and start[i] != 0, which means that the node i has an outgoing edge but no incoming edge, then:
  - Create a variable named minWeight to store the minimum weight of the component. Initialize it to INT_MAX.
  - Call the function dfs(i, minWeight, start, weights) and store the result in another variable, say last, the last node of the component. Note that the variable minWeight should be passed by reference.
  - Create an array/list of size three, store the value of i, last, and minWeight in it, and add it to the res array.
Finally, return the res array.

dfs(src, &minWeight, start[], weights[]):

If start[src] == 0, then return src as this is the last node of the component.
Update minWeight to min(minWeight, weights[src]).
Call the function recursively by passing start[src] as the src, i.e., return dfs(start[src], minWeight, start, weights).

Solve now

02 Approach

The idea is exactly similar to the previous approach, but here we will use a Breadth-First Search instead of a Depth-First Search.

Steps:

Create three arrays named to start, end, and weights to store the graph. Each array should be of size N + 1.
Run a loop i = 0 to M and do:
- Let’s denote edges[i][0] as src, edges[i][1] as dest and edges[i][2] as weight.
- Make start[src] = dest, weights[src] = weight and end[dest] = src.
Create an array/list to store the result, i.e., the starting and ending of each component along with the minimum weight in each component. Let’s name this array as res.
Run a loop from i = 1 to N and do:
- If end[i] == 0 and start[i] != 0, which means that the node i has an outgoing edge but no incoming edge, then:
  - Create a variable named minWeight to store the minimum weight of the component. Initialize it to INT_MAX.
  - Call the function bfs(i, minWeight, start, weights) and store the result in another variable, say last, the last node of the component. Note that the variable minWeight should be passed by reference.
  - Create an array/list of size three, store the value of i, last, and minWeight in it, and add it to the res array.
Finally, return the res array.

bfs(src, &minWeight, start[], weights[]):

While start[src] is not equal to 0 do:
- Update minWeight to min(minWeight, weights[src]).
- Make src = start[src].
Finally, return src, as this is the last node of the component.

Solve now