Posts published in “Graph”

花花酱 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];

}

};

花花酱 LeetCode 1782. Count Pairs Of Nodes

By zxi on March 6, 2021

You are given an undirected graph represented by an integer n, which is the number of nodes, and edges, where edges[i] = [u_i, v_i] which indicates that there is an undirected edge between u_i and v_i. You are also given an integer array queries.

The answer to the j^th query is the number of pairs of nodes (a, b) that satisfy the following conditions:

a < b
cnt is strictly greater than queries[j], where cnt is the number of edges incident to a or b.

Return an array answers such that answers.length == queries.length and answers[j] is the answer of the j^th query.

Note that there can be repeated edges.

Example 1:

Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The number of edges incident to at least one of each pair is shown above.

Example 2:

Input: n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
Output: [10,10,9,8,6]

Constraints:

2 <= n <= 2 * 10⁴
1 <= edges.length <= 10⁵
1 <= u_i, v_i <= n
u_i!= v_i
1 <= queries.length <= 20
0 <= queries[j] < edges.length

Solution 1: Pre-compute

Pre-compute # of pairs with total edges >= k. where k is from 0 to max_degree * 2 + 1.

Time complexity: (|node_degrees|² + V + E)
Space complexity: O(V+E)

C++

// Author: huahua

class Solution {

public:

vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {

vector<int> node_degrees(n);

unordered_map<int, int> edge_freq;

for (auto& e : edges) {

sort(begin(e), end(e));

++node_degrees[--e[0]];

++node_degrees[--e[1]];

++edge_freq[(e[0] << 16) | e[1]];

}

const int max_degree = *max_element(begin(node_degrees),

end(node_degrees));

// Need pad one more to handle "not found / 0" case.

vector<int> counts(max_degree * 2 + 2);

unordered_map<int, int> degree_count;

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

++degree_count[node_degrees[i]];

for (auto& [d1, c1] : degree_count)

for (auto& [d2, c2] : degree_count)

// Only count once if degrees are different to ensure (a < b)

if (d1 < d2) counts[d1 + d2] += c1 * c2;

// If degrees are the same C(n, 2) to ensure (a < b)

else if (d1 == d2) counts[d1 * 2] += c1 * (c1 - 1) / 2;

for (auto& [key, freq] : edge_freq) {

const int u = key >> 16;

const int v = key & 0xFFFF;

// For a pair of (u, v) their actual edge count is

// d[u] + d[v] - freq[(u, v)] instead of d[u] + d[v]

counts[node_degrees[u] + node_degrees[v]] -= 1;

counts[node_degrees[u] + node_degrees[v] - freq] += 1;

}

// counts[i] = # of pairs whose total edges >= i

for (int i = counts.size() - 2; i >= 0; --i)

counts[i] += counts[i + 1];

vector<int> ans;

for (int q : queries)

ans.push_back(counts[min(q + 1, static_cast<int>(counts.size() - 1))]);

return ans;

}

};

花花酱 LeetCode 1761. Minimum Degree of a Connected Trio in a Graph

By zxi on February 13, 2021

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [u_i, v_i] indicates that there is an undirected edge between u_i and v_i.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= u_i, v_i <= n
u_i!= v_i
There are no repeated edges.

Solution: Brute Force

Try all possible Trios.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

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

vector<bitset<400>> g(n);

for (const auto& e : edges) {

g[e[0] - 1].set(e[1] - 1);

g[e[1] - 1].set(e[0] - 1);

}

size_t ans = INT_MAX;

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

for (int j = i + 1; j < n; ++j)

if (g[i][j])

for (int k = j + 1; k < n; ++k)

if (g[i][k] && g[j][k])

ans = min(ans, g[i].count() + g[j].count() + g[k].count() - 6);

return ans == INT_MAX ? -1 : ans;

}

};

花花酱 LeetCode 1733. Minimum Number of People to Teach

By zxi on January 23, 2021

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the i^th user knows, and
friendships[i] = [u_i, v_i] denotes a friendship between the users u_i and v_i.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn’t guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 2, yielding two users to teach.

Constraints:

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
All tuples (u_i,v_i) are unique
languages[i] contains only unique values

Solution: Brute Force

Enumerate all languages and see which one is the best.

If two friends speak a common language, we can skip counting them.

Time complexity: O(m*(n+|friendship|))
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {

const int m = languages.size();

vector<unordered_set<int>> langs;

for (auto& l : languages) {

sort(begin(l), end(l));

langs.emplace_back(begin(l), end(l));

}

for (auto& e : friendships) {

const auto& l0 = languages[--e[0]];

const auto& l1 = languages[--e[1]];

vector<int> common;

set_intersection(begin(l0), end(l0), begin(l1), end(l1), back_inserter(common));

if (common.size()) e[0] = e[1] = -1;

}

int ans = INT_MAX;

for (int i = 1; i <= n; ++i) {

vector<int> users(m);

for (const auto& e : friendships) {

// e[0] and e[1] have a common language, skip this edge

if (e[0] == -1) continue;

if (!langs[e[0]].count(i)) users[e[0]] = 1;

if (!langs[e[1]].count(i)) users[e[1]] = 1;

}

ans = min(ans, accumulate(begin(users), end(users), 0));

}

return ans;

}

};

花花酱 LeetCode 1719. Number Of Ways To Reconstruct A Tree

By zxi on January 9, 2021

You are given an array pairs, where pairs[i] = [x_i, y_i], and:

There are no duplicates.
x_i < y_i

Let ways be the number of rooted trees that satisfy the following conditions:

The tree consists of nodes whose values appeared in pairs.
A pair [x_i, y_i] exists in pairs if and only if x_i is an ancestor of y_i or y_i is an ancestor of x_i.
Note: the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

0 if ways == 0
1 if ways == 1
2 if ways > 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

Constraints:

1 <= pairs.length <= 10⁵
1 <= x_i< y_i <= 500
The elements in pairs are unique.

Solution: Bitset

Time complexity: O(E*V)
Space complexity: O(V^2)

C++

// Author: Huahua

class Solution {

public:

int checkWays(vector<vector<int>>& pairs) {

// Construct a map, key is the node, value is the accessible nodes.

unordered_map<int, bitset<501>> m;

for (auto& e : pairs)

m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1;

// The tree must have one+ node/root that has paths to all the nodes.

if (!any_of(begin(m), end(m), [&m](const auto& kv) {

return kv.second.count() == m.size();})) return 0;

int multiple = 0;

for (const auto& e : pairs) {

// For each pair, check whether one can be the parent of another

// that can conver all the children nodes.

const auto& all = m[e[0]] | m[e[1]];

const int r0 = m[e[0]] == all;

const int r1 = m[e[1]] == all;

if (r0 + r1 == 0) return 0;

// If both can be parents, there can be multiple trees.

multiple |= r0 * r1;

}

return 1 + multiple;

}

};

Python3

# Author: Huahua

class Solution:

def checkWays(self, pairs: List[List[int]]) -> int:

m = defaultdict(set)

for u, v in pairs:

m[u] |= set((u, v))

m[v] |= set((u, v))

if not any(len(m[x]) == len(m) for x in m):

return 0

multiple = 0

for u, v in pairs:

union = m[u] | m[v]

ru, rv = int(m[u] == union), int(m[v] == union)

if not ru + rv: return 0

multiple |= ru * rv

return 1 + multiple