← 返回 twosigma 的题目列表Redundant Connection: Underground Pipes
类型:online_judge
Problem Description
Given an undirected graph which represents cities connected by pipelines. Each pipeline is represented by an endpoint pair [u, v], which indicates that there is a direct pipeline between city u and city v. You're required to inspect this graph and ensure no redundant connections exist. For each redundant connection, cutting these connections should still keep the cities connected.
Write a function to find and return the first redundant connection (in the order it appears in the input list). The graph is provided as an edge list, with each edge formatted as [u, v].
Input
edges: A 2D integer array, with size n x 2
Constraints
n is the number of pipelines, 1 <= n <= 1000
For some i, there are no self-loops, i.e., edges[i][0] != edges[i][1]
Output
Return the first redundant connection as [u, v].
Examples
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
Example
Input
[[1, 2], [1, 3], [2, 3]]