1466. Reorder Routes to Make All Paths Lead to the City Zero

leetcode medium

#array#csharp#graph#hash-table#leetcode#medium#recursion#tree

Task

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.

В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.

Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

Гарантируется, что каждый город может добраться до города 0 после перенаправления.

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

Output: 3

Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

C# solution

matched/original

public class Solution {
    int count = 0;
    void Dfs(int node, int parent, Dictionary<int, List<Tuple<int, int>>> adj) {
        if (!adj.ContainsKey(node)) return;
        foreach (var nei in adj[node]) {
            int neighbor = nei.Item1;
            int sign = nei.Item2;
            if (neighbor != parent) {
                count += sign;
                Dfs(neighbor, node, adj);
            }
        }
    }
    public int MinReorder(int n, int[][] connections) {
        var adj = new Dictionary<int, List<Tuple<int, int>>>();
        foreach (var connection in connections) {
            if (!adj.ContainsKey(connection[0])) adj[connection[0]] = new List<Tuple<int, int>>();
            if (!adj.ContainsKey(connection[1])) adj[connection[1]] = new List<Tuple<int, int>>();
            adj[connection[0]].Add(Tuple.Create(connection[1], 1));
            adj[connection[1]].Add(Tuple.Create(connection[0], 0));
        }
        Dfs(0, -1, adj);
        return count;
    }
}

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:
    int count = 0;
    void Dfs(int node, int parent, unordered_map<int, List<Tuple<int, int>>> adj) {
        if (!adj.count(node)) return;
        foreach (var nei in adj[node]) {
            int neighbor = nei.Item1;
            int sign = nei.Item2;
            if (neighbor != parent) {
                count += sign;
                Dfs(neighbor, node, adj);
            }
        }
    }
    public int MinReorder(int n, int[][] connections) {
        var adj = new unordered_map<int, List<Tuple<int, int>>>();
        foreach (var connection in connections) {
            if (!adj.count(connection[0])) adj[connection[0]] = new List<Tuple<int, int>>();
            if (!adj.count(connection[1])) adj[connection[1]] = new List<Tuple<int, int>>();
            adj[connection[0]].push_back(Tuple.Create(connection[1], 1));
            adj[connection[1]].push_back(Tuple.Create(connection[0], 0));
        }
        Dfs(0, -1, adj);
        return count;
    }
}

Java solution

matched/original

class Solution {
    int count = 0;

    public void dfs(int node, int parent, Map<Integer, List<List<Integer>>> adj) {
        if (!adj.containsKey(node)) {
            return;
        }
        for (List<Integer> nei : adj.get(node)) {
            int neighbor = nei.get(0);
            int sign = nei.get(1);
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    public int minReorder(int n, int[][] connections) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[1], 1));
            adj.computeIfAbsent(connection[1], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[0], 0));
        }
        dfs(0, -1, adj);
        return count;
    }
}

JavaScript solution

matched/original

var minReorder = function(n, connections) {
    let count = 0;
    const adj = new Map();
    for (const [a, b] of connections) {
        if (!adj.has(a)) adj.set(a, []);
        if (!adj.has(b)) adj.set(b, []);
        adj.get(a).push([b, 1]);
        adj.get(b).push([a, 0]);
    }

    const dfs = (node, parent) => {
        if (!adj.has(node)) return;
        for (const [neighbor, sign] of adj.get(node)) {
            if (neighbor !== parent) {
                count += sign;
                dfs(neighbor, node);
            }
        }
    };

    dfs(0, -1);
    return count;
};

Explanation

Algorithm

Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎