Posts published in “Graph”

花花酱 LeetCode 2477. Minimum Fuel Cost to Report to the Capital

By zxi on November 26, 2022

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [a_i, b_i] denotes that there exists a bidirectional road connecting cities a_i and b_i.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Example 1:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: 
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₂ goes directly to the capital with 1 liter of fuel.
- Representative₃ goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7
Explanation: 
- Representative₂ goes directly to city 3 with 1 liter of fuel.
- Representative₂ and representative₃ go together to city 1 with 1 liter of fuel.
- Representative₂ and representative₃ go together to the capital with 1 liter of fuel.
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₅ goes directly to the capital with 1 liter of fuel.
- Representative₆ goes directly to city 4 with 1 liter of fuel.
- Representative₄ and representative₆ go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

Input: roads = [], seats = 1
Output: 0
Explanation: No representatives need to travel to the capital city.

Constraints:

1 <= n <= 10⁵
roads.length == n - 1
roads[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
roads represents a valid tree.
1 <= seats <= 10⁵

Solution: Greedy + DFS

To reach the minimum cost, we must share cars if possible, say X reps from children nodes to an intermediate node u on the way towards capital 0. Then they all changes cars at node u, and we need (X + 1) // seats cars/fuel from u to 0.

We use DFS to count # of reps at each node u while accumulating the total cost.

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

C++

// Author: Huahua

class Solution {

public:

long long minimumFuelCost(vector<vector<int>>& roads, int seats) {

long long ans = 0;

vector<vector<int>> g(roads.size() + 1);

for (const vector<int>& r : roads) {

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

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

}

// Returns total # of children of u.

function<int(int, int)> dfs = [&](int u, int p, int rep = 1) {

for (int v : g[u])

if (v != p) rep += dfs(v, u);

if (u) ans += (rep + seats - 1) / seats;

return rep;

};

dfs(0, -1);

return ans;

}

};

花花酱 LeetCode 2374. Node With Highest Edge Score

By zxi on August 14, 2022

You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge.

The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].

The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.

Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.

Example 1:

Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.

Example 2:

Input: edges = [2,0,0,2]
Output: 0
Explanation:
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.

Constraints:

n == edges.length
2 <= n <= 10⁵
0 <= edges[i] < n
edges[i] != i

Solution:

Use an array to store the score of each node.

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

use max_element to find the largest element.

C++

// Author: Huahua

class Solution {

public:

int edgeScore(vector<int>& edges) {

const int n = edges.size();

vector<long> s(n);

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

s[edges[i]] += i;

return max_element(begin(s), end(s)) - begin(s);

}

};

花花酱 LeetCode 133. Clone Graph

By zxi on August 14, 2022

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List neighbors;
}

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100
Node.val is unique for each node.
There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.

Solution: DFS + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

Node* cloneGraph(Node* node) {

if (!node) return nullptr;

unordered_map<Node*, Node*> m;

function<void(Node*)> dfs = [&](Node* u) {

m[u] = new Node(u->val);

for (Node* v : u->neighbors) {

if (!m.count(v)) dfs(v);

m[u]->neighbors.push_back(m[v]);

}

};

dfs(node);

return m[node];

}

};

花花酱 LeetCode 2316. Count Unreachable Pairs of Nodes in an Undirected Graph

By zxi on June 25, 2022

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a_i, b_i] denotes that there exists an undirected edge connecting nodes a_i and b_i.

Return the number of pairs of different nodes that are unreachable from each other.

Example 1:

Input: n = 3, edges = [[0,1],[0,2],[1,2]]
Output: 0
Explanation: There are no pairs of nodes that are unreachable from each other. Therefore, we return 0.

Example 2:

Input: n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
Output: 14
Explanation: There are 14 pairs of nodes that are unreachable from each other:
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].
Therefore, we return 14.

Constraints:

1 <= n <= 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
There are no repeated edges.

Solution 1: DFS

Use DFS to find all CCs

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

C++

// Author: Huahua

// Author: Huahua, 791ms, 136 MB

class Solution {

public:

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

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> seen(n);

long long cur = 0;

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

++cur;

for (int v : g[u])

if (seen[v]++ == 0) dfs(v);

};

long long ans = 0;

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

if (seen[i]++) continue;

cur = 0;

dfs(i);

ans += (n - cur) * cur;

}

return ans / 2;

}

};

Solution 2: Union Find

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> parents(n);

vector<int> counts(n, 1);

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

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

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

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

};

for (const auto& e : edges) {

int ru = find(e[0]);

int rv = find(e[1]);

if (ru != rv) {

parents[rv] = ru;

counts[ru] += counts[rv];

}

long long ans = 0;

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

ans += n - counts[find(i)];

return ans / 2;

}

};

花花酱 LeetCode 2192. All Ancestors of a Node in a Directed Acyclic Graph

By zxi on March 11, 2022

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] = [from_i, to_i] denotes that there is a unidirectional edge from from_i to to_i in the graph.

Return a list answer, where answer[i] is the list of ancestors of the i^th node, sorted in ascending order.

A node u is an ancestor of another node v if u can reach v via a set of edges.

Example 1:

Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.

Example 2:

Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.

Constraints:

1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= from_i, to_i <= n - 1
from_i != to_i
There are no duplicate edges.
The graph is directed and acyclic.

Solution: DFS

For each source node S, add it to all its reachable nodes by traversing the entire graph.
In one pass, only traverse each child node at most once.

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

C++

// Author: Huahua

class Solution {

public:

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

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

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

for (const auto& e : edges)

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

function<void(int, int)> dfs = [&](int s, int u) -> void {

for (int v : g[u]) {

if (ans[v].empty() || ans[v].back() != s) {

ans[v].push_back(s);

dfs(s, v);

}

};

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

dfs(i, i);

return ans;

}

};