Graph Traversal Algorithms

MediumPython

Problem

Abzooba models relationships between services as an undirected graph. Given the number of services, their connections, and two selected services, return every connected component and a shortest path between the selected services.

Implement analyze_graph(n, edges, source, target).

Formal Specification

n is an integer representing vertices 0 through n - 1.
edges is a list of two-element lists [u, v], where each pair represents an undirected edge between valid vertices.
source and target are valid vertex integers.
Return a dictionary with:
- components: all connected components, with each component sorted in ascending order and the list of components sorted by their smallest vertex.
- path: any shortest path from source to target, including both endpoints, or [] if no path exists.

Use graph traversal algorithms rather than enumerating every possible path. The graph may contain isolated vertices, but it contains no duplicate edges or self-loops.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
Each edge endpoint is an integer in [0, n - 1]
The graph has no duplicate edges or self-loops
The graph is undirected

Function Signature

def analyze_graph(n, edges, source, target):

Implement analyze_graph(n, edges, source, target).

Formal Specification

n is an integer representing vertices 0 through n - 1.
edges is a list of two-element lists [u, v], where each pair represents an undirected edge between valid vertices.
source and target are valid vertex integers.
Return a dictionary with:
- components: all connected components, with each component sorted in ascending order and the list of components sorted by their smallest vertex.
- path: any shortest path from source to target, including both endpoints, or [] if no path exists.

Use graph traversal algorithms rather than enumerating every possible path. The graph may contain isolated vertices, but it contains no duplicate edges or self-loops.