Minimum Weight In A Connected Component

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Microsoft

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6 3
1 2 5
3 4 8
6 5 10
9 6
1 2 5
2 3 1
3 4 8
5 6 10
6 8 9
7 9 15
Sample Output 1 :
3
1 2 5
3 4 8
6 5 10
3
1 4 1
5 8 9
7 9 15
Explanation For Sample Input 1 :
For the first test case, the given graph is depicted in the below figure.

graph_input1_ex1

For the second test case, the given graph is depicted in the below figure.

graph_input1_ex2

Sample Input 2 :
2
2 1
2 1 8
6 5
1 2 7
2 3 9
3 4 10
4 5 12
5 6 2
Sample Output 2 :
1
2 1 8
1
1 6 2
Hint

Think of a DFS based approach.

Approaches (2)
DFS

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).
Time Complexity

O(N + M), where N and M denote the number of nodes and the graph’s number of edges.

 

We are traversing each node of the graph, and the dfs function runs for each edge of the graph, so the overall time complexity is O(N + M).

Space Complexity

O(N), where N denotes the number of nodes in the graph.

 

We are making three arrays start, end, weights of size N, and the res array of size C, where C is the number of components in the graph. Since C < N, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Weight In A Connected Component
Full screen
Console