Amazon Hub Network

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given 'N' Amazon distribution hubs, labeled from 0 to N-1, and a list of existing transport routes. Each route[i] = [u, v] represents a direct, bi-directional route between hub u and hub v.

You are allowed to add at most one new transport route between any two hubs that are not already connected.

Your task is to determine if it is possible to make the entire network of hubs fully connected by adding at most one new route. A network is fully connected if every hub is reachable from every other hub through some path of routes. Return true if it's possible, and false otherwise.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'N', the number of hubs.

The second line contains an integer 'E', the number of existing routes.

The next 'E' lines each contain two space-separated integers, u and v, representing a route.

Output Format:

Print true if the network can be made fully connected by adding at most one route.

Otherwise, print false.

Note:

The problem boils down to counting the number of connected components in the initial graph.

A connected component is a group of hubs where every hub can reach every other hub within that group.

   If the initial graph has 1 connected component, it's already fully connected. No new routes are needed. The answer is true.

   If the initial graph has 2 connected components, we can add one route between a hub in the first component and a hub in the second, merging them into a single component. The answer is true.

   If the initial graph has 3 or more connected components, adding one route can at most reduce the component count by one (e.g., from 3 to 2). It's impossible to make the network fully connected. The answer is false.

Sample Input 1:

Sample Output 1:

true

Explanation for Sample 1:

There are two separate groups of hubs: `{0, 1}` and `{2, 3}`. This is 2 connected components.
By adding a single new route, for example between hub 1 and hub 2, we can connect these two groups into one large, fully connected network.

Sample Input 2:

Sample Output 2:

false

Explanation for Sample 2:

There are three separate groups: `{0, 1}`, `{2, 3}`, and `{4, 5}`. This is 3 connected components.
Adding one route can only connect two of these groups. For example, connecting 1 and 2 would result in `{0, 1, 2, 3}` and `{4, 5}`. We would still have two components left. It is impossible to connect all of them with only one new route.

Expected Time Complexity:

The expected time complexity is O(N + E), as it requires a single traversal of the graph to count the components.

Constraints:

2 <= N <= 10^5
0 <= E <= 10^5
0 <= u, v < N

Time limit: 1 sec

Approaches (1)

Approach 1

Amazon Hub Network

Time Complexity

Space Complexity

(100% EXP penalty)

Amazon Hub Network

Console