Graph

Problem You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi. Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0). Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 109] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct. ...

Problem Given a positive integer N, find the smallest number of steps it will take to reach 1. There are two kinds of permitted steps: You may decrement N to N - 1. If a * b = N, you may decrement N to the larger of a and b. Examples Example 1: Input: N = 100 Output: 5 Explanation: 100 -> 1 with the following route: `100 -> 10 -> 9 -> 3 -> 2 -> 1`. ...

Problem In a directed graph, each node is assigned an uppercase letter. We define a path’s value as the number of most frequently-occurring letter along that path. For example, if a path in the graph goes through “ABACA”, the value of the path is 3, since there are 3 occurrences of ‘A’ on the path. Given a graph with n nodes and m directed edges, return the largest value path of the graph. If the largest value is infinite, then return null. ...

Problem A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes. ...

Problem You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph. Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order. ...

Problem You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1. You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi. You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects. ...

Problem There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node. You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph. ...

Depth First Search DFS Traversal for Graph The idea Depth-First Search (DFS) is a graph traversal algorithm that explores as deeply as possible along each branch before backtracking to explore other options. This is similar to how we play a maze game. DFS can be implemented iteratively using a stack data structure, similar to Breadth-First Search (BFS) which utilizes a queue. Alternatively, a recursive approach is very natural for DFS due to its depth-oriented exploration. We will explore both implementations in detail later. ...

Definition An Euler graph (or Eulerian graph) is a graph in which there exists a closed walk that visits every edge exactly once. This specific closed walk is called an Eulerian Circuit or Eulerian Cycle. Origins Most people have probably heard of the famous Seven Bridges of Königsberg problem. If not, please read about it on Wikipedia or below. The city of Königsberg (now Kaliningrad, Russia) was situated on both banks of the Pregel River and included two large islands connected to each other and the mainland by seven bridges. ...

Problem You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. ...