Pset 9 hints

Hints.md

Hints

Subgraphs

Hint #1

Use DFS for this. Approach is the same as with BFS (refer to session 7 slides), except that you use DFS.

Dijkstra

Hint #0

This is classic dijkstra with no twist. Copy code from lecture slides lol.

Hint #1

Do note that instead of being a vector > adj, where adj[i] -> vector of all neighbours to i, a weighted graph has vector > > adj, where adj[i] -> vector of pairs of {neighbour to i, weight of edge connecting i to neighbour}.

MRT

Hint #0

Copy algo from slides lol

Hint #1

Do note that instead of being a vector > adj, where adj[i] -> vector of all neighbours to i, a weighted graph has vector > > adj, where adj[i] -> vector of pairs of {neighbour to i, weight of edge connecting i to neighbour}.

Hint #2

Remember to resize dist and fill it all with INF properly.

Employee

The statement was not clear! Note:

1. An employee cannot be its own boss.
2. The graph is one component

Hint 1

Its solvable in a single dfs.

knightmoves

Hint #1

The board is a graph. Generate valid next positions as your neighbours. It's a quirky DFS depth question.

erp

Hint #1

It is two dijkstras - one at 0 and one at N-1.

boundlessboxes

Hint #1

multisource bfs.

exoticplants

Hint #1

understand the dijkstra algorithm.