Leetcode 1971. Find if Path Exists in Graph

難易度

Easy

アプローチ

BFS

class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {

        if(source == destination){
            return true;
        }

        ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            arrayList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int origin = edge[0];
            int dest = edge[1];

            arrayList.get(origin).add(dest);
            arrayList.get(dest).add(origin);
        }

        boolean[] isVisited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(source);
        isVisited[source] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();

            for(int i = 0 ; i < arrayList.get(now).size();i++){
                int next = arrayList.get(now).get(i);

                if(next == destination){
                    return true;
                }
                if(isVisited[next]){
                    continue;
                }
                isVisited[next] = true;
                queue.add(next);
            }
        }
        return false;
    }
}