379. Clone a Graph

Given an undirected graph with n vertices (0-indexed) and m edges, and a start vertex known to be part of it, simulate cloning only the connected component reachable from that start vertex (the graph may have cycles, and may have other components disconnected from the start). Print two lines: the reachable vertices in ascending order, space-separated, and then the number of edges among them.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains two space-separated integers u and v, an undirected edge (cycles are possible). The final line contains the start vertex. Output: Print two lines: the reachable vertices from the start in ascending order space-separated, then the number of edges among them.

1 <= n <= 10^5

A vertex from a SEPARATE, disconnected component must NOT appear in the output at all, even if it exists elsewhere in the overall graph - only vertices genuinely reachable from the given start vertex are part of this cloned component.

Simulate cloning just the connected component of a graph reachable from a given starting vertex. Brute force: Check every vertex in the whole graph against reachability from the start individually - this is less direct than a single BFS/DFS sweep that naturally discovers exactly the reachable set in one pass. Optimised: A single BFS/DFS from the start vertex, with visited tracking, naturally discovers EXACTLY the connected component reachable from it - counting qualifying edges (both endpoints in this discovered set) afterward avoids ever needing to construct actual duplicate graph objects.

Use the same adjacency-list BFS/DFS to find the reachable component and mark reachability in a boolean array, but instead of iterating each reachable vertex's neighbor list and correcting for double counting, make a single pass over the original edge list and count an edge only when both of its endpoints are marked reachable. This counts each edge exactly once with no division or double-counting correction needed, giving the cleanest and most direct linear-time computation of both the reachable set and the edge count. Time: O(n+m) Space: O(n+m)

Build an n x n adjacency matrix from the edge list, then run a BFS or DFS from the start vertex using the matrix to find every reachable vertex, scanning an entire row per vertex visited. Once the reachable set is known, count edges among them by checking every pair of reachable vertices against the matrix for an entry. This is correct but the matrix representation and the pairwise check both cost work proportional to n^2 regardless of how sparse the actual graph is. Time: O(n^2) Space: O(n^2)

Build an adjacency list from the edges and run BFS or DFS from the start vertex to find the reachable component in time proportional to its size. Then, for every reachable vertex, iterate its adjacency list and count how many of its neighbors are also reachable (using a boolean 'reachable' marker array for O(1) membership checks); since each edge between two reachable vertices gets counted once from each endpoint, divide the running total by two at the end to get the true edge count. This is close to optimal but requires the extra division-by-two correction from double counting. Time: O(n+m) Space: O(n+m)

1. Clone with a BFS or DFS starting from the given vertex. 2. Mark each vertex VISITED the moment it's DISCOVERED, so a cycle in the graph doesn't cause the same node to be 'cloned' twice or cause infinite recursion. 3. The 'cloned' edge count is simply the number of original edges whose BOTH endpoints ended up in the reachable set - no need to build actual new edge objects to count them.

Time: O(n + m) - the BFS/DFS visits every reachable vertex and edge at most once. Space: O(n), for the visited-tracking set and the reachable-vertex collection.

a start vertex whose component is a single isolated vertex (0 edges), a cycle within the reachable component, other disconnected components that must be excluded, and n at its maximum of 10^5.

Be ready to clarify that 'simulating cloning' here really just means correctly identifying the reachable SUBGRAPH (vertices and edges) - no actual new graph objects need to be constructed to answer what's asked.