1059. All Paths from Source Lead to Destination

LeetCode medium оригинал: C# #array #csharp #graph #hash-table #leetcode #medium #recursion #search

LeetCode Static

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2

Output: false

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class Solution {
    public bool LeadsToDestination(int n, int[][] edges, int source, int destination) {
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
        }
        
        var visited = new int[n];
        
        return Dfs(graph, visited, source, destination);
    }
    
    private bool Dfs(Dictionary<int, List<int>> graph, int[] visited, int node, int destination) {
        if (visited[node] != 0) return visited[node] == 2;
        if (!graph.ContainsKey(node)) return node == destination;
        visited[node] = 1;
        foreach (var neighbor in graph[node]) {
            if (!Dfs(graph, visited, neighbor, destination)) return false;
        }
        visited[node] = 2;
        return true;
    }
}

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 bool LeadsToDestination(int n, int[][] edges, int source, int destination) {
        var graph = new unordered_map<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.count(edge[0])) graph[edge[0]] = new List<int>();
            graph[edge[0]].push_back(edge[1]);
        }
        
        var visited = new int[n];
        
        return Dfs(graph, visited, source, destination);
    }
    
    private bool Dfs(unordered_map<int, List<int>> graph, vector<int>& visited, int node, int destination) {
        if (visited[node] != 0) return visited[node] == 2;
        if (!graph.count(node)) return node == destination;
        visited[node] = 1;
        foreach (var neighbor in graph[node]) {
            if (!Dfs(graph, visited, neighbor, destination)) return false;
        }
        visited[node] = 2;
        return true;
    }
}

Java решение

сопоставлено/оригинал

import java.util.*;

public class Solution {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
        }
        
        int[] visited = new int[n];
        
        return dfs(graph, visited, source, destination);
    }
    
    private boolean dfs(Map<Integer, List<Integer>> graph, int[] visited, int node, int destination) {
        if (visited[node] != 0) {
            return visited[node] == 2;
        }
        if (!graph.containsKey(node)) {
            return node == destination;
        }
        visited[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (!dfs(graph, visited, neighbor, destination)) {
                return false;
            }
        }
        visited[node] = 2;
        return true;
    }
}

JavaScript решение

сопоставлено/оригинал

var leadsToDestination = function(n, edges, source, destination) {
    const graph = {};
    for (const [a, b] of edges) {
        if (!graph[a]) graph[a] = [];
        graph[a].push(b);
    }

    const visited = new Array(n).fill(0);

    function dfs(node) {
        if (visited[node] !== 0) return visited[node] === 2;
        if (!graph[node]) return node === destination;
        visited[node] = 1;
        for (const neighbor of graph[node]) {
            if (!dfs(neighbor)) return false;
        }
        visited[node] = 2;
        return true;
    }

    return dfs(source);
};

Python решение

сопоставлено/оригинал

def leadsToDestination(n, edges, source, destination):
    from collections import defaultdict
    
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
    
    visited = [0] * n
    
    def dfs(node):
        if visited[node] != 0:
            return visited[node] == 2
        if not graph[node]:
            return node == destination
        visited[node] = 1
        for neighbor in graph[node]:
            if not dfs(neighbor):
                return False
        visited[node] = 2
        return True

    return dfs(source)

Go решение

сопоставлено/оригинал

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    graph := make(map[int][]int)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    
    visited := make([]int, n)
    
    var dfs func(node int) bool
    dfs = func(node int) bool {
        if visited[node] != 0 {
            return visited[node] == 2
        }
        if len(graph[node]) == 0 {
            return node == destination
        }
        visited[node] = 1
        for _, neighbor := range graph[node] {
            if !dfs(neighbor) {
                return false
            }
        }
        visited[node] = 2
        return true
    }

    return dfs(source)
}

Algorithm

Построение графа и проверка путей:

Построить граф на основе входных данных.

Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

Проверка конечности путей:

Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.

Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

Рекурсивная проверка конечности путей:

Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.