Depth-First Search
Breadth-First Search
Union Find
Graph
Description
In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n
nodes labeled from 1
to n
, with one additional edge added. The added edge has two different vertices chosen from 1
to n
, and was not an edge that already existed. The graph is represented as an array edges
of length n
where edges[i] = [ai , bi ]
indicates that there is an edge between nodes ai
and bi
in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n
nodes . If there are multiple answers, return the answer that occurs last in the input.
Example 1:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Example 2:
Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Constraints:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
There are no repeated edges.
The given graph is connected.
Solutions
Solution 1
Python3 Java C++ Go JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def findRedundantConnection ( self , edges : List [ List [ int ]]) -> List [ int ]:
def find ( x ):
if p [ x ] != x :
p [ x ] = find ( p [ x ])
return p [ x ]
p = list ( range ( 1010 ))
for a , b in edges :
if find ( a ) == find ( b ):
return [ a , b ]
p [ find ( a )] = find ( b )
return []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
private int [] p ;
public int [] findRedundantConnection ( int [][] edges ) {
p = new int [ 1010 ] ;
for ( int i = 0 ; i < p . length ; ++ i ) {
p [ i ] = i ;
}
for ( int [] e : edges ) {
int a = e [ 0 ] , b = e [ 1 ] ;
if ( find ( a ) == find ( b )) {
return e ;
}
p [ find ( a ) ] = find ( b );
}
return null ;
}
private int find ( int x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ] );
}
return p [ x ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
vector < int > p ;
vector < int > findRedundantConnection ( vector < vector < int >>& edges ) {
p . resize ( 1010 );
for ( int i = 0 ; i < p . size (); ++ i ) p [ i ] = i ;
for ( auto & e : edges ) {
int a = e [ 0 ], b = e [ 1 ];
if ( find ( a ) == find ( b )) return e ;
p [ find ( a )] = find ( b );
}
return {};
}
int find ( int x ) {
if ( p [ x ] != x ) p [ x ] = find ( p [ x ]);
return p [ x ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func findRedundantConnection ( edges [][] int ) [] int {
p := make ([] int , 1010 )
for i := range p {
p [ i ] = i
}
var find func ( x int ) int
find = func ( x int ) int {
if p [ x ] != x {
p [ x ] = find ( p [ x ])
}
return p [ x ]
}
for _ , e := range edges {
a , b := e [ 0 ], e [ 1 ]
if find ( a ) == find ( b ) {
return e
}
p [ find ( a )] = find ( b )
}
return [] int {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 /**
* @param {number[][]} edges
* @return {number[]}
*/
var findRedundantConnection = function ( edges ) {
let p = Array . from ({ length : 1010 }, ( _ , i ) => i );
function find ( x ) {
if ( p [ x ] != x ) {
p [ x ] = find ( p [ x ]);
}
return p [ x ];
}
for ( let [ a , b ] of edges ) {
if ( find ( a ) == find ( b )) {
return [ a , b ];
}
p [ find ( a )] = find ( b );
}
return [];
};
GitHub