685. Redundant Connection II
В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.
Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.
Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.
Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
C# решение
сопоставлено/оригиналpublic class Solution {
public int[] FindRedundantDirectedConnection(int[][] edges) {
int N = edges.Length;
var parent = new Dictionary<int, int>();
var candidates = new List<int[]>();
foreach (var edge in edges) {
if (parent.ContainsKey(edge[1])) {
candidates.Add(new int[] { parent[edge[1]], edge[1] });
candidates.Add(edge);
} else {
parent[edge[1]] = edge[0];
}
}
int root = Orbit(1, parent).Node;
if (candidates.Count == 0) {
var cycle = Orbit(root, parent).Seen;
foreach (var edge in edges) {
if (cycle.Contains(edge[0]) && cycle.Contains(edge[1])) {
return edge;
}
}
}
var children = parent.GroupBy(kvp => kvp.Value).ToDictionary(g => g.Key, g => g.Select(kvp => kvp.Key).ToList());
var seen = new bool[N + 1];
var stack = new Stack<int>();
stack.Push(root);
while (stack.Count > 0) {
int node = stack.Pop();
if (!seen[node]) {
seen[node] = true;
if (children.ContainsKey(node)) {
foreach (int c in children[node]) stack.Push(c);
}
}
}
return seen.Any(b => !b) ? candidates[0] : candidates[1];
}
public class OrbitResult {
public int Node { get; }
public HashSet<int> Seen { get; }
public OrbitResult(int node, HashSet<int> seen) {
Node = node;
Seen = seen;
}
}
public OrbitResult Orbit(int node, Dictionary<int, int> parent) {
var seen = new HashSet<int>();
while (parent.ContainsKey(node) && !seen.Contains(node)) {
seen.Add(node);
node = parent[node];
}
return new OrbitResult(node, seen);
}
}C++ решение
auto-draft, проверить перед отправкой#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:
public vector<int>& FindRedundantDirectedConnection(int[][] edges) {
int N = edges.size();
var parent = new unordered_map<int, int>();
var candidates = new List<int[]>();
foreach (var edge in edges) {
if (parent.count(edge[1])) {
candidates.push_back(new int[] { parent[edge[1]], edge[1] });
candidates.push_back(edge);
} else {
parent[edge[1]] = edge[0];
}
}
int root = Orbit(1, parent).Node;
if (candidates.size() == 0) {
var cycle = Orbit(root, parent).Seen;
foreach (var edge in edges) {
if (cycle.Contains(edge[0]) && cycle.Contains(edge[1])) {
return edge;
}
}
}
var children = parent.GroupBy(kvp => kvp.Value).ToDictionary(g => g.Key, g => g.Select(kvp => kvp.Key).ToList());
var seen = new bool[N + 1];
var stack = new stack<int>();
stack.push(root);
while (stack.size() > 0) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.count(node)) {
foreach (int c in children[node]) stack.push(c);
}
}
}
return seen.Any(b => !b) ? candidates[0] : candidates[1];
}
public class OrbitResult {
public int Node { get; }
public HashSet<int> Seen { get; }
public OrbitResult(int node, HashSet<int> seen) {
Node = node;
Seen = seen;
}
}
public OrbitResult Orbit(int node, unordered_map<int, int> parent) {
var seen = new HashSet<int>();
while (parent.count(node) && !seen.Contains(node)) {
seen.push_back(node);
node = parent[node];
}
return new OrbitResult(node, seen);
}
}Java решение
сопоставлено/оригиналclass Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int N = edges.length;
Map<Integer, Integer> parent = new HashMap<>();
List<int[]> candidates = new ArrayList<>();
for (int[] edge : edges) {
if (parent.containsKey(edge[1])) {
candidates.add(new int[]{parent.get(edge[1]), edge[1]});
candidates.add(edge);
} else {
parent.put(edge[1], edge[0]);
}
}
int root = orbit(1, parent).node;
if (candidates.isEmpty()) {
Set<Integer> cycle = orbit(root, parent).seen;
for (int[] edge : edges) {
if (cycle.contains(edge[0]) && cycle.contains(edge[1])) {
return edge;
}
}
}
Map<Integer, List<Integer>> children = new HashMap<>();
for (int v : parent.keySet()) {
int pv = parent.get(v);
children.computeIfAbsent(pv, k -> new ArrayList<>()).add(v);
}
boolean[] seen = new boolean[N + 1];
Stack<Integer> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!seen[node]) {
seen[node] = true;
if (children.containsKey(node)) {
stack.addAll(children.get(node));
}
}
}
for (boolean b : seen) {
if (!b) {
return candidates.get(0);
}
}
return candidates.get(1);
}
public OrbitResult orbit(int node, Map<Integer, Integer> parent) {
Set<Integer> seen = new HashSet<>();
while (parent.containsKey(node) && !seen.contains(node)) {
seen.add(node);
node = parent.get(node);
}
return new OrbitResult(node, seen);
}
}
class OrbitResult {
int node;
Set<Integer> seen;
OrbitResult(int n, Set<Integer> s) {
node = n;
seen = s;
}
}Go решение
сопоставлено/оригиналpackage main
type Solution struct{}
func (s *Solution) findRedundantDirectedConnection(edges [][]int) []int {
N := len(edges)
parent := make(map[int]int)
var candidates [][]int
for _, edge := range edges {
if p, exists := parent[edge[1]]; exists {
candidates = append(candidates, []int{p, edge[1]})
candidates = append(candidates, edge)
} else {
parent[edge[1]] = edge[0]
}
}
root := s.orbit(1, parent).node
if len(candidates) == 0 {
cycle := s.orbit(root, parent).seen
ans := []int{0, 0}
for _, edge := range edges {
if cycle[edge[0]] && cycle[edge[1]] {
ans = edge
}
}
return ans
}
children := make(map[int][]int)
for v, pv := range parent {
children[pv] = append(children[pv], v)
}
seen := make([]bool, N+1)
seen[0] = true
stack := []int{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if !seen[node] {
seen[node] = true
for _, c := range children[node] {
stack = append(stack, c)
}
}
}
for _, b := range seen {
if !b {
return candidates[0]
}
}
return candidates[1]
}
type OrbitResult struct {
node int
seen map[int]bool
}
func (s *Solution) orbit(node int, parent map[int]int) *OrbitResult {
seen := make(map[int]bool)
for {
if _, exists := parent[node]; !exists || seen[node] {
break
}
seen[node] = true
node = parent[node]
}
return &OrbitResult{node, seen}
}Algorithm
Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра.
Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл.
Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.