Posts tagged as “graph”

花花酱 LeetCode 2092. Find All People With Secret

By zxi on November 28, 2021

You are given an integer n indicating there are n people numbered from 0 to n - 1. You are also given a 0-indexed 2D integer array meetings where meetings[i] = [x_i, y_i, time_i] indicates that person x_i and person y_i have a meeting at time_i. A person may attend multiple meetings at the same time. Finally, you are given an integer firstPerson.

Person 0 has a secret and initially shares the secret with a person firstPerson at time 0. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person x_i has the secret at time_i, then they will share the secret with person y_i, and vice versa.

The secrets are shared instantaneously. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return a list of all the people that have the secret after all the meetings have taken place. You may return the answer in any order.

Example 1:

Input: n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
Output: [0,1,2,3,5]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

Example 2:

Input: n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
Output: [0,1,3]
Explanation:
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

Example 3:

Input: n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
Output: [0,1,2,3,4]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

Example 4:

Input: n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
Output: [0,1,2,3]
Explanation:
At time 0, person 0 shares the secret with person 1.
At time 1, person 0 shares the secret with person 2, and person 1 shares the secret with person 3.
Thus, people 0, 1, 2, and 3 know the secret after all the meetings.

Constraints:

2 <= n <= 10⁵
1 <= meetings.length <= 10⁵
meetings[i].length == 3
0 <= x_i, y_i<= n - 1
x_i != y_i
1 <= time_i <= 10⁵
1 <= firstPerson <= n - 1

Solution: Union Find

Sorting meetings by time.

At each time stamp, union people who meet.
Key step: “un-union” people if they DO NOT connected to 0 / known the secret after each timestamp.

Time complexity: O(nlogn + m + n)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {

map<int, vector<pair<int, int>>> events;

for (const auto& m : meetings)

events[m[2]].emplace_back(m[0], m[1]);

vector<int> p(n);

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

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

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

};

p[firstPerson] = 0;

for (const auto& [t, s] : events) {

for (const auto [u, v] : s)

p[find(u)] = find(v);

for (const auto [u, v] : s) {

if (find(u) != find(0)) p[u] = u;

if (find(v) != find(0)) p[v] = v;

}

vector<int> ans;

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

if (find(i) == find(0)) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 2050. Parallel Courses III

By zxi on November 18, 2021

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)^th course.

You must find the minimum number of months needed to complete all the courses following these rules:

You may start taking a course at any time if the prerequisites are met.
Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Constraints:

1 <= n <= 5 * 10⁴
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)
relations[j].length == 2
1 <= prevCourse_j, nextCourse_j <= n
prevCourse_j != nextCourse_j
All the pairs [prevCourse_j, nextCourse_j] are unique.
time.length == n
1 <= time[i] <= 10⁴
The given graph is a directed acyclic graph.

Solution: Topological Sorting

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

C++

// Author: Huahua

class Solution {

public:

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {

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

for (const auto& r: relations)

g[r[0] - 1].push_back(r[1] - 1);

vector<int> t(n, -1);

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

if (t[u] != -1) return t[u];

t[u] = 0;

for (int v : g[u])

t[u] = max(t[u], dfs(v));

return t[u] += time[u];

};

int ans = 0;

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

ans = max(ans, dfs(i));

return ans;

}

};

Python3

class Solution:

def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:

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

for u, v in relations: g[u - 1].append(v - 1)

@cache

def dfs(u: int) -> int:

return max([dfs(v) for v in g[u]] + [0]) + time[u]

return max(dfs(u) for u in range(n))

花花酱 LeetCode 2076. Process Restricted Friend Requests

By zxi on November 15, 2021

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [x_i, y_i] means that person x_i and person y_i cannot become friends,either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j are already direct friends, the request is still successful.

Example 1:

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

Example 2:

Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

Example 3:

Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

Constraints:

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Solution: Union Find / Brute Force

For each request, check all restrictions.

Time complexity: O(req * res)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {

vector<int> parents(n);

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

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

if (parents[x] == x) return x;

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

};

auto check = [&](int u, int v) {

for (const auto& r : restrictions) {

int pu = find(r[0]);

int pv = find(r[1]);

if ((pu == u && pv == v) || (pu == v && pv == u))

return false;

}

return true;

};

vector<bool> ans;

for (const auto& r : requests) {

int pu = find(r[0]);

int pv = find(r[1]);

if (pu == pv || check(pu, pv)) {

parents[pu] = pv;

ans.push_back(true);

} else {

ans.push_back(false);

}

return ans;

}

};

花花酱 LeetCode 2049. Count Nodes With the Highest Score

By zxi on October 26, 2021

There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1.

Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees.

Return the number of nodes that have the highest score.

Example 1:

Input: parents = [-1,2,0,2,0]
Output: 3
Explanation:
- The score of node 0 is: 3 * 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 * 1 * 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

Example 2:

Input: parents = [-1,2,0]
Output: 2
Explanation:
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 * 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

Constraints:

n == parents.length
2 <= n <= 10⁵
parents[0] == -1
0 <= parents[i] <= n - 1 for i != 0
parents represents a valid binary tree.

Solution: Recursion

Write a function that returns the element of a subtree rooted at node.

We can compute the score based on:
1. size of the subtree(s)
2. # of children

Root is a special case whose score is max(c[0], 1) * max(c[1], 1).

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

C++

// Author: Huahua

class Solution {

public:

int countHighestScoreNodes(vector<int>& parents) {

const int n = parents.size();

long high = 0;

int ans = 0;

vector<vector<int>> tree(n);

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

tree[parents[i]].push_back(i);

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

long c[2] = {0, 0};

for (int i = 0; i < tree[node].size(); ++i)

c[i] = dfs(tree[node][i]);

long score = 0;

if (node == 0) // case #1: root

score = max(c[0], 1l) * max(c[1], 1l);

else if (tree[node].size() == 0) // case #2: leaf

score = n - 1;

else if (tree[node].size() == 1) // case #3: one child

score = c[0] * (n - c[0] - 1);

else // case #4: two children

score = c[0] * c[1] * (n - c[0] - c[1] - 1);

if (score > high) {

high = score;

ans = 1;

} else if (score == high) {

++ans;

}

return 1 + c[0] + c[1];

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 2039. The Time When the Network Becomes Idle

By zxi on October 18, 2021

There is a network of n servers, labeled from 0 to n - 1. You are given a 2D integer array edges, where edges[i] = [u_i, v_i] indicates there is a message channel between servers u_i and v_i, and they can pass any number of messages to each other directly in one second. You are also given a 0-indexed integer array patience of length n.

All servers are connected, i.e., a message can be passed from one server to any other server(s) directly or indirectly through the message channels.

The server labeled 0 is the master server. The rest are data servers. Each data server needs to send its message to the master server for processing and wait for a reply. Messages move between servers optimally, so every message takes the least amount of time to arrive at the master server. The master server will process all newly arrived messages instantly and send a reply to the originating server via the reversed path the message had gone through.

At the beginning of second 0, each data server sends its message to be processed. Starting from second 1, at the beginning of every second, each data server will check if it has received a reply to the message it sent (including any newly arrived replies) from the master server:

If it has not, it will resend the message periodically. The data server i will resend the message every patience[i] second(s), i.e., the data server i will resend the message if patience[i] second(s) have elapsed since the last time the message was sent from this server.
Otherwise, no more resending will occur from this server.

The network becomes idle when there are no messages passing between servers or arriving at servers.

Return the earliest second starting from which the network becomes idle.

Example 1:

Input: edges = [[0,1],[1,2]], patience = [0,2,1]
Output: 8
Explanation:
At (the beginning of) second 0,
- Data server 1 sends its message (denoted 1A) to the master server.
- Data server 2 sends its message (denoted 2A) to the master server.

At second 1,
- Message 1A arrives at the master server. Master server processes message 1A instantly and sends a reply 1A back.
- Server 1 has not received any reply. 1 second (1 < patience[1] = 2) elapsed since this server has sent the message, therefore it does not resend the message.
- Server 2 has not received any reply. 1 second (1 == patience[2] = 1) elapsed since this server has sent the message, therefore it resends the message (denoted 2B).

At second 2,
- The reply 1A arrives at server 1. No more resending will occur from server 1.
- Message 2A arrives at the master server. Master server processes message 2A instantly and sends a reply 2A back.
- Server 2 resends the message (denoted 2C).
...
At second 4,
- The reply 2A arrives at server 2. No more resending will occur from server 2.
...
At second 7, reply 2D arrives at server 2.

Starting from the beginning of the second 8, there are no messages passing between servers or arriving at servers.
This is the time when the network becomes idle.

Example 2:

Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
Output: 3
Explanation: Data servers 1 and 2 receive a reply back at the beginning of second 2.
From the beginning of the second 3, the network becomes idle.

Constraints:

n == patience.length
2 <= n <= 10⁵
patience[0] == 0
1 <= patience[i] <= 10⁵ for 1 <= i < n
1 <= edges.length <= min(10⁵, n * (n - 1) / 2)
edges[i].length == 2
0 <= u_i, v_i < n
u_i != v_i
There are no duplicate edges.
Each server can directly or indirectly reach another server.

Solution: Shortest Path

Compute the shortest path from node 0 to rest of the nodes using BFS.

Idle time for node i = (dist[i] * 2 – 1) / patince[i] * patience[i] + dist[i] * 2 + 1

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

C++

// Author: Huahua

class Solution {

public:

int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) {

const int n = patience.size();

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

for (const auto& e : edges) {

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

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

}

vector<int> ts(n, -1);

ts[0] = 0;

queue<int> q{{0}};

while (!q.empty()) {

int u = q.front(); q.pop();

for (int v : g[u]) {

if (ts[v] != -1) continue;

ts[v] = ts[u] + 1;

q.push(v);

}

int ans = 0;

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

int t = (ts[i] * 2 - 1) / patience[i] * patience[i] + ts[i] * 2 + 1;

ans = max(ans, t);

}

return ans;

}

};

Posts tagged as “graph”

花花酱 LeetCode 2092. Find All People With Secret

Solution: Union Find

C++

Related Problems

花花酱 LeetCode 2050. Parallel Courses III

Solution: Topological Sorting

C++

Python3

花花酱 LeetCode 2076. Process Restricted Friend Requests

C++

花花酱 LeetCode 2049. Count Nodes With the Highest Score

Solution: Recursion

C++

花花酱 LeetCode 2039. The Time When the Network Becomes Idle

Solution: Shortest Path

C++