New update is available. Click here to update.

Last Updated: 23 Dec, 2020

Difficulty: Moderate

```
Consider a country having 4 states numbered from 1 to 4. These 4 states are connected by 5 bidirectional roads given as :
1 --- 2 with cost = 8
2 --- 3 with cost = 6
3 --- 4 with cost = 5
1 --- 4 with cost = 2
1 --- 3 with cost = 4
The map of the country can be represented as:
```

```
Now, the best way to choose 3 roads is:
```

```
The cost of travelling from any state to all other states is 2 + 4 + 6 i.e. 12.
```

```
The first line contains an integer 'T' denoting the number of test cases or queries to be run.
The first line of each test case or query contains two space-separated integers 'N' and ‘M’ representing the number of states and number of roads in the country, respectively.
The next 'N' lines of every test case contain three single space-separated integers ‘A’, ‘B’ and ‘C’, representing a road between the states 'A' and 'B' and 'C' denoting the cost of travelling them.
```

```
For each test case, print 'N' - 1 lines each containing 3 space separated integers 'A', 'B' and 'C' representing the road you have chosen and the cost to traverse that road.
```

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

```
1 <= 'T' <= 10
1 <= 'N' <= 1000
'N' - 1 <= 'M' <= 2000
1 <= 'C' <= 10^6
Time limit: 1 sec
```

The idea is to create a graph of the country with states as its vertices and roads as edges.

For creating a graph we will use an adjacency matrix representation of graph **Cost** with **Cost[i][j]** representing the cost of travelling from state **i** to state **j** and vice versa, state **j** to **i**.

The very first approach to solve this problem is using Prim’s algorithm, which is a greedy algorithm.

The idea behind Prim’s algorithm is simple, a spanning tree means all states must be connected.

- Firstly, we start with an empty spanning tree.
- We bifurcate the states in 2 groups:
- The first group contains the states already included in the
**MST**. - The other group contains the states not yet included.

- The first group contains the states already included in the
- At every step, it considers all the roads that connect the two groups and picks the minimum weight road from these roads or minimum weight state from the second group.
- After picking the road, it adds the state of the second group into the first group ( MST group).

**Algorithm:**

- Firstly, create an adjacency matrix of the given roads and costs.
- Create a
**visited**array of size N that keeps track of states already included in MST. Initially mark all states as unvisited. - Create a
**weight**array of size N, to assign a**weight**value to all states in the input graph. Initialize all weight values as INFINITE. Assign the weight value as 0 for the first state so that it is picked first. - While all states are not
**visited.**

- Pick a state
**A**which is not marked as**visited****weight**value. - Include
**A**to**visited**. - Now follow these steps:
- For each
**i**from**1**to**N**:- If there is a path between
**A**and**i**such that**i**is not marked as visited and weight of**i**is less than cost of road:- Update
**weight[i] = cost**of road**A - i**.

- Update

- If there is a path between

- For each

Let’s understand with the example :

Initially, all the states are marked unvisited and weight values of states are** {0, INF, INF, INF}**.

Now, pick the state with minimum weight. i.e. state 1 and mark it as visited.

After picking this state, update the weight values of all adjacent states of 1, which are 2 and 4 in this case to their corresponding costs.

The weight array becomes: **{0, 3, INF, 5}**.

Now, pick the next state with minimum weight which is not visited yet. i.e. state 2 and mark it as visited.

After marking state 2 visited, update the weight value of all the adjacent states of 2 which are not visited yet, i.e state 3 to their corresponding cost if and only if it is less than the one stored in the weight array.

The weight array becomes;** {0, 3, 1, 5}**.

Similarly, pick the next unvisited state with minimum weight i.e. 3 and mark it as visited.

Update weight values of adjacent states of state 3 which are not visited to their corresponding cost if and only if it is less than the one stored in the weight array.

In the above point, the adjacent states of 3 are 4 and 2.

- We need not interfere with state 2 as it is already visited.
- In case of state 4,
**weight[4]**is less than cost [3 to 4] i.e. 5 < 8, thus, we don’t update.

So, the final MST we get is,

The idea is to again create a graph of the country with states as its vertices and roads as edges.

But this time we will use an adjacency list representation of graph **adjList** with **adjList[i]** representing a vector of pair with first element of pair as the neighbour state of **i** say **A**, ans second element of pair is the cost of road between **i** and **A**.

- Create a
**visited**array that keeps track of states already included in MST. Initially mark all states as unvisited. - Create a
**weight**array.Initialize all weight values as**INFINITE**. - Assign the weight value as 0 for the first state so that it is picked first.
- Create a
**set**of size**N**where**N**is the number of states in the country. Every element of the set contains the weight value of state and the state number. **set**is not empty, do the following.- Extract the min weight value state from the
**set**. Let the extracted state be - Mark this state as
**visited**. - Update weight of all adjacent states of
**U**which are not visited yet.- For every adjacent state
**V**, if the cost of the road**from**U**to**V**V**, update the weight value of V**.**

- For every adjacent state

- Extract the min weight value state from the

SIMILAR PROBLEMS

Ninja and the experiment

Posted: 5 Sep, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Spiral Matrix

Posted: 24 Nov, 2022

Difficulty: Easy

Popular Interview Problems: