Posts tagged as “graph”

花花酱 LeetCode 2045. Second Minimum Time to Reach Destination

By zxi on October 17, 2021

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] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. 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.

Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.

Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.

Notes:

You can go through any vertex any number of times, including 1 and n.
You can assume that when the journey starts, all signals have just turned green.

Example 1:

Input: n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
Output: 13
Explanation:
The figure on the left shows the given graph.
The blue path in the figure on the right is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -> 4: 3 minutes, time elapsed=3
- 4 -> 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.

The red path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -> 3: 3 minutes, time elapsed=3
- 3 -> 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -> 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.

Example 2:

Input: n = 2, edges = [[1,2]], time = 3, change = 2
Output: 11
Explanation:
The minimum time path is 1 -> 2 with time = 3 minutes.
The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

Constraints:

2 <= n <= 10⁴
n - 1 <= edges.length <= min(2 * 10⁴, n * (n - 1) / 2)
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
There are no duplicate edges.
Each vertex can be reached directly or indirectly from every other vertex.
1 <= time, change <= 10³

Solution: Best first search

Since we’re only looking for second best, to avoid TLE, for each vertex, keep two best time to arrival is sufficient.

Time complexity: O(2ElogE)
Space complexity: O(V+E)

C++

// Author: Huahua

class Solution {

public:

int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {

vector<vector<int>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

priority_queue<pair<int, int>> q; // {-t, node}

q.emplace(0, 1);

int min_time = -1;

vector<vector<int>> ts(n + 1);

ts[1].push_back(0);

while (true) {

const int t = -q.top().first;

const int u = q.top().second;

if (u == n) {

if (min_time == -1 || t == min_time) {

min_time = t;

} else {

return t;

}

q.pop();

for (const auto& v : g[u]) {

const int tt = (((t / change) & 1) ? (t + change - t % change) : t) + time;

if ((ts[v].size() > 0 && tt == ts[v].back()) || ts[v].size() >= 2) continue;

ts[v].push_back(tt);

q.emplace(-tt, v);

}

return -1;

}

};

花花酱 LeetCode 1905. Count Sub Islands

By zxi on August 15, 2021

You are given two m x n binary matrices grid1 and grid2 containing only 0‘s (representing water) and 1‘s (representing land). An island is a group of 1‘s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

Example 1:

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2 
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints:

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] and grid2[i][j] are either 0 or 1.

Solution: Coloring

Give each island in grid1 a different color. Whiling using the same method to find island and coloring it in grid2, we also check whether the same cell in grid1 always has the same color.

Time complexity: O(mn)
Space complexity: O(1) modify in place or O(mn)

C++

// Author: Huahua

class Solution {

public:

int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {

const int m = grid1.size();

const int n = grid1[0].size();

int valid = 1;

function<void(int, int, int, int)> color = [&](int i, int j, int c, int p) {

if (i < 0 || i >= m || j < 0 || j >= n) return;

auto& gc = p ? grid2 : grid1;

auto& go = p ? grid1 : grid2;

if (gc[i][j] != 1) return;

gc[i][j] = c;

if (p && go[i][j] != c) valid = 0;

color(i + 1, j, c, p);

color(i - 1, j, c, p);

color(i, j + 1, c, p);

color(i, j - 1, c, p);

};

for (int i = 0, c = 2; i < m; ++i)

for (int j = 0; j < n; ++j)

if (grid1[i][j] == 1) color(i, j, c++, 0);

int ans = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

if (grid2[i][j] == 1 && grid1[i][j]) {

valid = 1;

color(i, j, grid1[i][j], 1);

ans += valid;

}

return ans;

}

};

花花酱 LeetCode 1857. Largest Color Value in a Directed Graph

By zxi on May 29, 2021

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x₁ -> x₂ -> x₃ -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints:

n == colors.length
m == edges.length
1 <= n <= 10⁵
0 <= m <= 10⁵
colors consists of lowercase English letters.
0 <= a_j, b_j < n

Solution: Topological Sorting

freq[n][c] := max freq of color c after visiting node n.

Time complexity: O(n)
Space complexity: O(n*26)

python

class Solution:

def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:

INF = 1e9

n = len(colors)

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

visited = [0] * n

freq = [[0] * 26 for _ in range(n)]

def dfs(u: int) -> int:

idx = ord(colors[u]) - ord('a')

if not visited[u]:

visited[u] = 1 # visiting

for v in g[u]:

if (dfs(v) == INF):

return INF

for c in range(26):

freq[u][c] = max(freq[u][c], freq[v][c])

freq[u][idx] += 1

visited[u] = 2 # done

return freq[u][idx] if visited[u] == 2 else INF

ans = 0

for u in range(n):

ans = max(ans, dfs(u))

if ans == INF: break

return -1 if ans == INF else ans

花花酱 LeetCode 1791. Find Center of Star Graph

By zxi on March 13, 2021

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] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

3 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Solution: Graph / Hashtable

Count the degree of each node, return the one with n-1 degrees.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findCenter(vector<vector<int>>& edges) {

unordered_map<int, int> degrees;

for (const auto& e : edges) {

++degrees[e[0]];

++degrees[e[1]];

}

const int n = degrees.size();

for (const auto& [id, d] : degrees)

if (d == n - 1) return id;

return -1;

}

};

Since the center node must appear in each edge, we just need to find the mode of edges[0] + edges[1]

Time complexity: O(1)
Space complexity: O(1)

Python

# Author: Huahua

class Solution:

def findCenter(self, e):

return mode(e[0] + e[1])

花花酱 LeetCode 1786. Number of Restricted Paths From First to Last Node

By zxi on March 6, 2021

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z₀, z₁,z₂, ..., z_k] such that z₀= start and z_k = end and there is an edge between z_i and z_i+1 where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(z_i) > distanceToLastNode(z_i+1) where 0 <= i <= k-1.

Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

Example 2:

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.

Constraints:

1 <= n <= 2 * 10⁴
n - 1 <= edges.length <= 4 * 10⁴
edges[i].length == 3
1 <= u_i, v_i <= n
u_i!= v_i
1 <= weight_i <= 10⁵
There is at most one edge between any two nodes.
There is at least one path between any two nodes.

Solution: Dijkstra + DFS w/ memoization

Find shortest path from n to all the nodes.
paths(u) = sum(paths(v)) if dist[u] > dist[v] and (u, v) has an edge
return paths(1)

Time complexity: O(ElogV + V + E)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int countRestrictedPaths(int n, vector<vector<int>>& edges) {

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Shortest distance from n to x.

vector<int> dist(n + 1, INT_MAX / 2);

dist[n] = 0;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (dist[u] < d) continue;

for (auto [v, w]: g[u]) {

if (dist[u] + w >= dist[v]) continue;

dist[v] = dist[u] + w;

q.emplace(dist[v], v);

}

vector<int> dp(n + 1, INT_MAX);

function<int(int)> dfs = [&](int u) {

if (u == n) return 1;

if (dp[u] != INT_MAX) return dp[u];

int ans = 0;

for (auto [v, w]: g[u])

if (dist[u] > dist[v])

ans = (ans + dfs(v)) % kMod;

return dp[u] = ans;

};

return dfs(1);

}

};

Combined

C++

// Author: Huahua

class Solution {

public:

int countRestrictedPaths(int n, vector<vector<int>>& edges) {

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Shortest distance from n to x.

vector<int> dist(n + 1, INT_MAX);

vector<int> dp(n + 1);

dist[n] = 0;

dp[n] = 1;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == 1) break;

for (auto [v, w]: g[u]) {

if (dist[v] > dist[u] + w)

q.emplace(dist[v] = dist[u] + w, v);

if (dist[v] > dist[u])

dp[v] = (dp[v] + dp[u]) % kMod;

}

return dp[1];

}

};