Posts tagged as “graph”

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

花花酱 LeetCode 1697. Checking Existence of Edge Length Limited Paths

By zxi on December 20, 2020

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [u_i, v_i, dis_i] denotes an edge between nodes u_i and v_i with distance dis_i. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [p_j, q_j, limit_j], your task is to determine for each queries[j] whether there is a path between p_j and q_jsuch that each edge on the path has a distance strictly less than limit_j .

Return a boolean array answer, where answer.length == queries.length and the j^th value of answer is true if there is a path for queries[j] is true, and false otherwise.

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

Constraints:

2 <= n <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
There may be multiple edges between two nodes.

Solution: Union Find

Since queries are offline, we can reorder them to optimize time complexity. Answer queries by their limits in ascending order while union edges by weights up to the limit. In this case, we just need to go through the entire edge list at most once.

Time complexity: O(QlogQ + ElogE)
Space complexity: O(Q + E)

C++

// Author: Huahua

class Solution {

public:

vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {

vector<int> parents(n);

iota(begin(parents), end(parents), 0);

function<int(int)> find = [&](int x) {

return parents[x] == x ? x : parents[x] = find(parents[x]);

};

const int m = Q.size();

for (int i = 0; i < m; ++i) Q[i].push_back(i);

// Sort edges by weight in ascending order.

sort(begin(E), end(E), [](const auto& a, const auto& b) { return a[2] < b[2]; });

// Sort queries by limit in ascending order

sort(begin(Q), end(Q), [](const auto& a, const auto& b) { return a[2] < b[2]; });

vector<bool> ans(m);

int i = 0;

for (const auto& q : Q) {

while (i < E.size() && E[i][2] < q[2])

parents[find(E[i++][0])] = find(E[i][1]);

ans[q[3]] = find(q[0]) == find(q[1]);

}

return ans;

}

};