Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где 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

👨‍💻 Алгоритм:

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

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

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

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний