Skip to content
BASA DSA

Redundant Connection

MediumGraphs

A tree on labels 1..n received one additional edge. Return an edge whose removal restores a tree; when several work, return the one appearing latest in the supplied edge array.

Example 1

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 1, node 1: 2, node 2: 3. Edges: node 0 (1) — node 1 (2); node 1 (2) — node 2 (3); node 0 (1) — node 2 (3).123
Undirected input edges; isolated vertices are included.

Input
edges = [[1,2],[2,3],[1,3]]
Output
[1,3]

Explanation

The final edge [1,3] closes the triangle; removing it restores a tree.

Example 2

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 1, node 1: 2, node 2: 3, node 3: 4, node 4: 5. Edges: node 0 (1) — node 1 (2); node 1 (2) — node 2 (3); node 2 (3) — node 3 (4); node 0 (1) — node 3 (4); node 0 (1) — node 4 (5).12345
Undirected input edges; isolated vertices are included.

Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output
[1,4]

Explanation

[1,4] closes cycle 1-2-3-4-1 and is its latest edge; node 5 stays attached.

Example 3

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 1, node 1: 2, node 2: 3. Edges: node 0 (1) — node 2 (3); node 2 (3) — node 1 (2); node 1 (2) — node 0 (1).123
Undirected input edges; isolated vertices are included.

Input
edges = [[1,3],[3,2],[2,1]]
Output
[2,1]

Explanation

[2,1] closes the three-node cycle and is the latest removable edge.

Constraints

  • 3 <= n <= 1000
  • There are n distinct undirected edges
  • No self-loops

Function contractfindRedundantConnectionArguments: json
Loading draft…
SolutionRuns on your device