Posts

Connected Components in a Graph II

-
Image
In reality this question is just looking for the following: find the connected components to vertex 1, and select the minimum edge. That's it. The problem statement guarantees that there will be at least one connection between 1 and N. That way, just traverse the graph looking for the smallest edge, starting from 1. Code is down below, cheers, ACC. Minimum Score of a Path Between Two Cities - LeetCode You are given a positive integer n representing n cities numbered from 1 to n . You are also given a 2D array roads where roads[i] = [a i , b i , distance i ] indicates that there is a bidirectional road between cities a i and b i with a distance equal to distance i . The cities graph is not necessarily connected. The score of a path between two cities is defined as the minimum distance of a road in this path. Return the minimum possible score of a path between cities 1 and n . Note : A path is a sequence of roads between two cities. It is allowed for a path to contain the s...
Post a Comment
Read more

Mapping a Tree to a HashTable data structure II

-
Another problem where it gets easier if you map the tree to a HashTable. Keep in mind that this is an N-Ary tree, not binary. After that it is a straightforward pre-order depth-first-search (Pre-Order DPS). Code is down below, cheers, ACC. Finish Time of Tasks I - LeetCode You are given an integer n representing the number of tasks in a project, numbered from 0 to n - 1 . These tasks are connected as a tree rooted at task 0. This is represented by a 2D integer array edges of length n - 1 , where edges[i] = [u i , v i ] indicates that task u i is the parent of task v i . You are also given an array baseTime of length n , where baseTime[i] represents the time to complete task i . The finish time of each task is calculated as follows: Leaf task: The finish time is baseTime[i] . Non-leaf task: Let earliest be the minimum finish time among its children, and latest be the maximum finish time among its children. Let ownDuration be (latest - earliest) + baseTime[i] . The finish ti...
Post a Comment
Read more