684. Redundant Connection Medium

1/**
2 * [684] Redundant Connection
3 *
4 * In this problem, a tree is an undirected graph that is connected and has no cycles.
5 * 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.
6 * 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.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-1-graph.jpg" style="width: 222px; height: 222px;" />
10 * Input: edges = [[1,2],[1,3],[2,3]]
11 * Output: [2,3]
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2021/05/02/reduntant1-2-graph.jpg" style="width: 382px; height: 222px;" />
15 * Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
16 * Output: [1,4]
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	n == edges.length
22 * 	3 <= n <= 1000
23 * 	edges[i].length == 2
24 * 	1 <= ai < bi <= edges.length
25 * 	ai != bi
26 * 	There are no repeated edges.
27 * 	The given graph is connected.
28 * 
29 */
30pub struct Solution {}
31
32// problem: https://leetcode.com/problems/redundant-connection/
33// discuss: https://leetcode.com/problems/redundant-connection/discuss/?currentPage=1&orderBy=most_votes&query=
34
35// submission codes start here
36
37impl Solution {
38    pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
39        vec![]
40    }
41}
42
43// submission codes end
44
45#[cfg(test)]
46mod tests {
47    use super::*;
48
49    #[test]
50    fn test_684() {
51    }
52}
53