# Posts tagged as “graph”

There areĀ NĀ network nodes, labelledĀ 1Ā toĀ N.

GivenĀ times, a list of travel times asĀ directedĀ edgesĀ times[i] = (u, v, w), whereĀ uĀ is the source node,Ā vĀ is the target node, andĀ wĀ is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain nodeĀ K. How long will it take for all nodes to receive the signal? If it is impossible, returnĀ -1.

Note:

1. NĀ will be in the rangeĀ [1, 100].
2. KĀ will be in the rangeĀ [1, N].
3. The length ofĀ timesĀ will be in the rangeĀ [1, 6000].
4. All edgesĀ times[i] = (u, v, w)Ā will haveĀ 1 <= u, v <= NĀ andĀ 1 <= w <= 100.

Idea:

Construct the graph and do a shortest path from K to all other nodes.

Solution 2:

C++ / Bellman-Ford

Time complexity: O(ne)

Space complexity: O(n)

Solution3:

C++ / Floyd-Warshall

Time complexity: O(n^3)

Space complexity: O(n^2)

v2

Problem:

Equations are given in the formatĀ A / B = k, whereĀ AĀ andĀ BĀ are variables represented as strings, andĀ kĀ is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, returnĀ -1.0.

Example:
GivenĀ a / b = 2.0, b / c = 3.0.
queries are:Ā a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
returnĀ [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is:Ā vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queriesĀ , whereĀ equations.size() == values.size(), and the values are positive. This represents the equations. ReturnĀ vector<double>.

According to the example above:

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

Ā

# Solution 2:Ā Union Find

## Python3

Related Problems:

Problem:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Idea:

Finding cycles O(n^2) -> Topological sort O(n)

# Solution 2: DFS Finding cycles

Time complexity: O(n^2)

Space complexity: O(n)

# Related Pr0blems:

Problem:

Given two words (beginWordĀ andĀ endWord), and a dictionary’s word list, find all shortest transformation sequence(s) fromĀ beginWordĀ toĀ endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note thatĀ beginWordĀ isĀ notĀ a transformed word.

For example,

Given:
beginWordĀ =Ā "hit"
endWordĀ =Ā "cog"
wordListĀ =Ā ["hot","dot","dog","lot","log","cog"]

Return

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assumeĀ beginWordĀ andĀ endWordĀ are non-empty and are not the same.

Idea:

BFS to construct the graph + DFS to extract the paths

Solutions:

C++, BFS 1

C++ / BFS 2

C++ / Bidirectional BFS

Problem:

Given a list of airline tickets represented by pairs of departure and arrival airportsĀ [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs fromĀ JFK. Thus, the itinerary must begin withĀ JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itineraryĀ ["JFK", "LGA"]Ā has a smaller lexical order thanĀ ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
ticketsĀ =Ā [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
ReturnĀ ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
ticketsĀ =Ā [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
ReturnĀ ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction isĀ ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Idea:

Convert the graph to a tree and do post-order traversal

Ā Solution: