3067. Count Pairs of Connectable Servers in a Weighted Tree Network

MediumTreeDepth-First SearchArray
Leetcode Link

Problem Description

In this problem, you are given a set of servers connected by weighted bidirectional edges, which together form an undirected tree graph. Each server is labeled with a unique number from 0 to n-1, where n is the number of servers. The connections between them are defined by the edges, where each edge is represented by a triplet [ai, bi, weighti] indicating a connection between server ai and bi with the weight weighti. In addition, you have a value signalSpeed that is used as a divisor to determine connectivity.

The task is to determine for every server in the tree how many pairs of servers (a and b) can be connectable through it. Two servers are considered connectable through a third server c if all of the following conditions are met:

  • a < b and both a and b are distinct from c.
  • The distance from server c to a is exactly divisible by the signalSpeed.
  • The distance from server c to b is also exactly divisible by the signalSpeed.
  • The paths from c to a and c to b do not have common edges.

The result should be an array count, where count[i] represents the number of server pairs that are connectable through server i.

Intuition

To solve this problem, we devise an approach that leverages Depth-First Search (DFS). We will need to count the number of servers that are at a distance divisible by signalSpeed from each server, and then we will need to determine how many unique pairs of servers can be formed through that server.

The first step is to represent the network of servers using an adjacency list g, which will allow us to traverse the graph efficiently and find the neighbors of any given server.

Next, for each server a, we can consider it as a potential intermediate connecting server. Starting from a, we visit all directly connected neighbors b using DFS. While traversing the graph, we keep accumulating the count of nodes reachable from a via b at distances that are divisible by signalSpeed. We perform this count by invoking dfs(b, a, w) where b is the neighbor node, a is the current node, and w is the weight of the edge connecting them.

As we move through the tree, we keep a cumulative count s of nodes reachable from previous neighbors. When we calculate the count t for a new neighbor, we update the number of connectable server pairs for server a by adding s * t to it. This represents the number of new unique pairs that can be formed by combining servers reachable from previous neighbors with servers reachable from the current neighbor. After evaluating all neighbors of a, we will have the total number of connectable server pairs through a.

After iterating through all servers in this manner, we obtain the desired count of connectable server pairs for each server, which we return as the result.

Learn more about Tree and Depth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution approach uses Depth-First Search (DFS) which is a common algorithm for traversing or searching through tree structures. DFS is a good fit for this problem because it allows us to explore all the paths from a given server to its descendent servers, thereby calculating distances and checking divisibility by signalSpeed.

Here's how the algorithm is implemented:

  1. Construct an adjacency list g; for each edge [a, b, w] in the edges list, add an entry such that g[a] includes the tuple (b, w), representing a neighbor b and the weight of the edge w from a to b, and vice versa since it's an undirected graph.

  2. Create an array ans initialized with zeros to store the resulting counts of connectable server pairs for each server.

  3. For each server a, we want to find the number of connectable server pairs that include a as an intermediate server.

  4. Initialize a count s to 0, representing the cumulative count of servers found through previous neighbors of server a.

  5. For each neighbor b with edge weight w connected to a:

    • Perform a DFS to calculate the number t of servers connectable starting from b such that the distance to a (accumulated in a variable ws within the DFS) is divisible by signalSpeed.
    • The DFS function dfs(a, fa, ws) receives the current server a, its parent server fa, and the current weight sum ws. The function returns the number of servers reachable from a with the sum of edge weights divisible by signalSpeed.

  6. Use the count t from the DFS to update the answer for the current server a. The number of new connectable pairs is s * t because each server counted by s can form a pair with each server counted by t. Add this number to ans[a].

  7. Update the cumulative count s by adding t to it, for the next iterations. This step is crucial because it accumulates the total number of servers that can be connected through a from all its neighbors.

  8. After computing this for all neighbors b of a server a, you end up with the total count of server pairs that can connect through a, stored in ans[a].

  9. Repeat steps 4-8 for each server in the graph to fill the array ans with the total count of connectable server pairs for all servers.

  10. Return the array ans which now contains the required result for each server in the tree.

This algorithm works efficiently due to the tree's properties, which ensure there are no cycles, and each distinct path from a node a to any other nodes in its subtree can be explored exactly once by DFS without revisiting nodes, thus avoiding redundant calculations, and enabling the solution approach to work in polynomial time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example Walkthrough

Let's consider a small example with 4 servers and signalSpeed = 2 to illustrate the solution approach.

1Servers (number of servers, n): 4
2signalSpeed: 2
3edges: [[0, 1, 2], [1, 2, 4], [1, 3, 2]]

Our tree graph for servers will look like this:

1    0
2    |
3    |(weight: 2)
4    |
5    1
6   / \
7  /   \
8 /     \
92       3
10 (weight: 4)   (weight: 2)

Step 1: Construct the adjacency list g from the edges:

1g[0] = [(1, 2)]
2g[1] = [(0, 2), (2, 4), (3, 2)]
3g[2] = [(1, 4)]
4g[3] = [(1, 2)]

Step 2: Initialize an array ans with zeros [0, 0, 0, 0] to hold the counts for each server.

Step 3: We'll iterate over each server to find the number of connectable server pairs.

Step 4-7: For server 0, the neighbor is server 1 with an edge weight of 2, we perform a DFS starting from server 1. Since we are only interested in servers that are connectable through server 0, we find servers 2 and 3 are both reachable from 1 with distances divisible by signalSpeed = 2. Since server 1 has two connectable servers, there is only one pair (2, 3) that can be routed through it. So we add 1 to ans[0].

Step 4-7: For server 1, we see three potential paths (one through 0, one through 2, and one through 3). Through DFS for each neighbor, we find the following:

  • Server 0 contributes 0 connectable servers.
  • Server 2 contributes 1 connectable server (itself).
  • Server 3 contributes 1 connectable server (itself). Combining the paths from 2 and 3, as 2 < 3, gives us 1 pair. Hence, we add 1 to ans[1].

Servers 2 and 3 have only one neighbor they connect to without common edges, which is server 1, and no server pairs (a, b) such that a < b are connectable through them. Hence, ans[2] and ans[3] remain 0.

Step 9: After iterating over all servers, the ans array values are finalized as [1, 1, 0, 0].

Step 10: The final output [1, 1, 0, 0] is returned, indicating that through server 0, 1 pair of servers can be connected, the same for server 1, and no connectable pairs through servers 2 and 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countPairsOfConnectableServers(
5        self, connections: List[List[int]], signal_speed: int
6    ) -> List[int]:
7        # Helper function to perform depth-first search and count the number of pairs
8        def dfs(node: int, parent: int, total_weight: int) -> int:
9            pair_count = 1 if total_weight % signal_speed == 0 else 0
10            for neighbor, weight in graph[node]:
11                if neighbor != parent:
12                    pair_count += dfs(neighbor, node, total_weight + weight)
13            return pair_count
14              
15        # Calculate the total number of nodes (servers)
16        num_nodes = len(connections) + 1
17        # Initialize a graph from the connection data
18        graph = [[] for _ in range(num_nodes)]
19        for src, dest, weight in connections:
20            graph[src].append((dest, weight))
21            graph[dest].append((src, weight))
22      
23        # Initialize a list to store the answer for each node
24        answer = [0] * num_nodes
25        # Loop through each node to find count of connectable server pairs
26        for node in range(num_nodes):
27            cumulative_pairs = 0
28            # Iterate over the connections for the current node
29            for neighbor, weight in graph[node]:
30                # Count pairs for each connection
31                pairs = dfs(neighbor, node, weight)
32                # Update the answer list using the half-pair technique
33                answer[node] += cumulative_pairs * pairs
34                # Update the cumulative count of pairs for the next connections
35                cumulative_pairs += pairs
36        return answer
37
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    private int signalSpeed;                             // The speed of the signal as defined.
7    private List<int[]>[] adjacencyList;                // This list represents the graph as an adjacency list.
8
9    // Method to count pairs of connectable servers given the edges and signal speed.
10    public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
11        int numServers = edges.length + 1;                   // Number of servers is one more than the number of edges.
12        this.signalSpeed = signalSpeed;                      // Set the global signal speed.
13        adjacencyList = new List[numServers];                // Initialize the adjacency list for each server.
14        Arrays.setAll(adjacencyList, x -> new ArrayList<>());
15        // Convert the edge list to an adjacency list representation of the graph.
16        for (int[] edge : edges) {
17            int from = edge[0], to = edge[1], weight = edge[2];
18            adjacencyList[from].add(new int[] {to, weight});
19            adjacencyList[to].add(new int[] {from, weight});
20        }
21        int[] answer = new int[numServers];                  // Initialize an array to store the counts for each server.
22        // Iterate over each server to find connectable pairs by using depth-first search.
23        for (int server = 0; server < numServers; ++server) {
24            int count = 0;
25            // Explore all reachable servers from the current one and calculate counts.
26            for (int[] edge : adjacencyList[server]) {
27                int neighbor = edge[0], weight = edge[1];
28                int reachableServers = dfs(neighbor, server, weight);
29                answer[server] += count * reachableServers;
30                count += reachableServers;
31            }
32        }
33        return answer;                                    // Return the answer array containing counts for each server.
34    }
35
36    // Helper method for depth-first search to count reachable servers given a certain accumulated weight.
37    private int dfs(int current, int parent, int accumulatedWeight) {
38        // If the accumulated weight is a multiple of the signal speed, it means this server is connectable.
39        int connectableServers = accumulatedWeight % signalSpeed == 0 ? 1 : 0;
40        // Explore all connected servers from the current server.
41        for (int[] edge : adjacencyList[current]) {
42            int nextServer = edge[0], weight = edge[1];
43            // Avoid visiting the server from which the current DFS initiated.
44            if (nextServer != parent) {
45                connectableServers += dfs(nextServer, current, accumulatedWeight + weight);
46            }
47        }
48        return connectableServers;                          // Return the count of reachable connectable servers.
49    }
50}
51
1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7    vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
8        // Determine the number of servers in the network (nodes in the graph)
9        int numServers = edges.size() + 1;
10
11        // Create a graph represented as an adjacency list with pairs of connected server and link weight
12        vector<pair<int, int>> graph[numServers];
13      
14        // Populate the graph with the given edges and their weights
15        for (auto& edge : edges) {
16            int serverA = edge[0], serverB = edge[1], weight = edge[2];
17            graph[serverA].emplace_back(serverB, weight);
18            graph[serverB].emplace_back(serverA, weight);
19        }
20
21        // Lambda function for depth-first search to count connectable pairs
22        function<int(int, int, int)> dfs = [&](int server, int parent, int cumulativeWeight) {
23            // Count the server as connectable if the cumulative weight is multiple of signalSpeed
24            int count = cumulativeWeight % signalSpeed == 0;
25            // Traverse the connected servers
26            for (auto& [connectedServer, edgeWeight] : graph[server]) {
27                if (connectedServer != parent) {
28                    // Add the count of connectable servers in the subtree
29                    count += dfs(connectedServer, server, cumulativeWeight + edgeWeight);
30                }
31            }
32            return count;
33        };
34
35        // Vector to store the count of connectable pairs of servers for each server
36        vector<int> counts(numServers);
37
38        // Iterate through each server to calculate the connectable pairs
39        for (int server = 0; server < numServers; ++server) {
40            int connectableCount = 0;
41            // Iterate through the connected servers and add to the pair count
42            for (auto& [connectedServer, edgeWeight] : graph[server]) {
43                int tempCount = dfs(connectedServer, server, edgeWeight);
44                counts[server] += connectableCount * tempCount;
45                // Update the connectable count with the recently found count
46                connectableCount += tempCount;
47            }
48        }
49
50        // Return the vector containing counts for each server
51        return counts;
52    }
53};
54
1function countPairsOfConnectableServers(edges: number[][], signalSpeed: number): number[] {
2    // n represents the total number of servers.
3    const numServers = edges.length + 1;
4    // graph is used to store the connectivity information as an adjacency list.
5    const graph: [number, number][][] = Array.from({ length: numServers }, () => []);
6
7    // Convert the edge list into an adjacency list.
8    for (const [from, to, weight] of edges) {
9        graph[from].push([to, weight]);
10        graph[to].push([from, weight]);
11    }
12
13    // Depth-first search function to count the number of times the sum of weights is divisible by the signal speed.
14    const depthFirstSearch = (current: number, parent: number, totalWeight: number): number => {
15        let count = totalWeight % signalSpeed === 0 ? 1 : 0;
16        for (const [neighbor, weight] of graph[current]) {
17            if (neighbor !== parent) {
18                count += depthFirstSearch(neighbor, current, totalWeight + weight);
19            }
20        }
21        return count;
22    };
23
24    // Initialize an array to hold the answers.
25    const answer: number[] = Array(numServers).fill(0);
26
27    // Iterate over each server to compute pairs of connectable servers.
28    for (let server = 0; server < numServers; ++server) {
29        let subCount = 0;
30        for (const [neighbor, weight] of graph[server]) {
31            const countFromNeighbor = depthFirstSearch(neighbor, server, weight);
32            answer[server] += subCount * countFromNeighbor;
33            subCount += countFromNeighbor;
34        }
35    }
36
37    // Return the answer array.
38    return answer;
39}
40
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

The time complexity of the given code is O(n^2). This is because for each of the n nodes, there is a Depth-First Search (DFS) that is initiated. DFS itself may visit each node one time in the worst case, and since the DFS is occurring in a loop of n nodes, this results in a potential of n * (n-1) operations, hence the O(n^2).

Furthermore, within the DFS function, there is a check for whether ws % signalSpeed is equal to zero that occurs with each recursive call, but this does not add to the complexity in terms of n, as it is a constant-time operation.

The space complexity of the code is O(n). The primary space usage comes from the adjacency list g, which contains a list for each of the n nodes. Each list hold pairs ((b, w)) representing edges and their weights. There is also the ans array of size n that is kept throughout the execution. Temporary variables such as cnt and the stack frames due to recursive calls do not increase the overall space complexity, as they will at most be proportional to the depth of the recursion which is at most n, in the case of a path graph.

Additionally, the recursive nature of the DFS function does entail a call stack, which could have a depth of up to n in a worst-case scenario (such as a linear tree), but since the adjacency list is the dominant space-consuming structure and they are both of O(n) space complexity, the overall space complexity remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫