684. Redundant Connection
В этой задаче tree — это неориентированный graph, который является связным и не содержит циклов.
Вам дан graph, который изначально был treeм с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное edge. Добавленное edge соединяет две разные вершины, выбранные из 1 до n, и это edge не существовало ранее. graph представлен arrayом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует edge между узлами ai и bi в graphе.
return edge, которое можно удалить, чтобы результирующий graph стал treeм из n узлов. Если существует несколько ответов, return тот, который встречается последним в исходных данных.
Example:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
HashSet<int> seen = new HashSet<int>();
const int MAX_EDGE_VAL = 1000;
public int[] FindRedundantConnection(int[][] edges) {
List<int>[] graph = new List<int>[MAX_EDGE_VAL + 1];
for (int i = 0; i <= MAX_EDGE_VAL; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
seen.Clear();
if (graph[edge[0]].Count > 0 && graph[edge[1]].Count > 0 &&
Dfs(graph, edge[0], edge[1])) {
return edge;
}
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
throw new InvalidOperationException("No redundant connection found");
}
public bool Dfs(List<int>[] graph, int source, int target) {
if (!seen.Contains(source)) {
seen.Add(source);
if (source == target) return true;
foreach (int nei in graph[source]) {
if (Dfs(graph, nei, target)) return true;
}
}
return false;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
HashSet<int> seen = new HashSet<int>();
const int MAX_EDGE_VAL = 1000;
public vector<int>& FindRedundantConnection(int[][] edges) {
List<int>[] graph = new List<int>[MAX_EDGE_VAL + 1];
for (int i = 0; i <= MAX_EDGE_VAL; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
seen.Clear();
if (graph[edge[0]].size() > 0 && graph[edge[1]].size() > 0 &&
Dfs(graph, edge[0], edge[1])) {
return edge;
}
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
throw new InvalidOperationException("No redundant connection found");
}
public bool Dfs(List<int>[] graph, int source, int target) {
if (!seen.Contains(source)) {
seen.push_back(source);
if (source == target) return true;
foreach (int nei in graph[source]) {
if (Dfs(graph, nei, target)) return true;
}
}
return false;
}
}Java solution
matched/originalclass Solution {
Set<Integer> seen = new HashSet<>();
int MAX_EDGE_VAL = 1000;
public int[] findRedundantConnection(int[][] edges) {
ArrayList<Integer>[] graph = new ArrayList[MAX_EDGE_VAL + 1];
for (int i = 0; i <= MAX_EDGE_VAL; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : edges) {
seen.clear();
if (!graph[edge[0]].isEmpty() && !graph[edge[1]].isEmpty() &&
dfs(graph, edge[0], edge[1])) {
return edge;
}
graph[edge[0]].add(edge[1]);
graph[edge[1]].add(edge[0]);
}
throw new AssertionError();
}
public boolean dfs(ArrayList<Integer>[] graph, int source, int target) {
if (!seen.contains(source)) {
seen.add(source);
if (source == target) return true;
for (int nei : graph[source]) {
if (dfs(graph, nei, target)) return true;
}
}
return false;
}
}Python solution
matched/originalclass Solution:
def __init__(self):
self.seen = set()
self.MAX_EDGE_VAL = 1000
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
graph = [[] for _ in range(self.MAX_EDGE_VAL + 1)]
for edge in edges:
self.seen.clear()
if graph[edge[0]] and graph[edge[1]] and self.dfs(graph, edge[0], edge[1]):
return edge
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return []
def dfs(self, graph: List[List[int]], source: int, target: int) -> bool:
if source not in self.seen:
self.seen.add(source)
if source == target:
return True
for nei in graph[source]:
if self.dfs(graph, nei, target):
return True
return FalseGo solution
matched/originalpackage main
func findRedundantConnection(edges [][]int) []int {
const MAX_EDGE_VAL = 1000
graph := make([][]int, MAX_EDGE_VAL+1)
for i := range graph {
graph[i] = make([]int, 0)
}
seen := make(map[int]bool)
var dfs func(source, target int) bool
dfs = func(source, target int) bool {
if !seen[source] {
seen[source] = true
if source == target {
return true
}
for _, nei := range graph[source] {
if dfs(nei, target) {
return true
}
}
}
return false
}
for _, edge := range edges {
seen = make(map[int]bool)
if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) {
return edge
}
graph[edge[0]] = append(graph[edge[0]], edge[1])
graph[edge[1]] = append(graph[edge[1]], edge[0])
}
return nil
}Algorithm
Для каждого ребра (u, v) создайте представление graphа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.
Выполняйте обход в глубину для каждого ребра, временно удаляя его из graphа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это edge является дублирующимся.
return дублирующееся edge, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.