[LeetCode/Easy] 1971. Find if Path Exists in Graph

1. Input

1) int n

- 그래프의 노드의 개수

- 노드에는 0번부터 n-1번까지의 번호가 붙어 있다.

2) int[][] edges

- edges[i] = [u_i, v_i]. u_i번 노드와 v_i번 노드가 연결되어 있다.

3) int source

4) int destination

 

2. Output

1) 주어진 그래프에서 source에서 destination으로 가는 경로가 있다면 true, 없다면 false를 반환

 

3. Constraint

1) 1 <= n <= 2 * 10^5

2) 0 <= edges.length <= 2 * 10^5

3) edges[i].length == 2

4) 0 <= u_i, v_i <= n - 1

5) u_i != v_i

6) 0 <= source, destination <= n - 1

7) 중복되거나 자기 자신을 가리키는 간선은 없다.

 

4. Example

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 -> Output: true

설명: 0번에서 2번까지 가는 경로는 2가지가 있다.

- 0 -> 1 -> 2

- 0 -> 2

 

5. Code

1) 첫 코드(2023/06/21)

class Solution {
    static int[] parent;

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        parent = new int[n];
        for(int i=1 ; i<n ; i++)
            parent[i] = i;
        
        for(int i=0 ; i<edges.length ; i++)
            union(edges[i][0], edges[i][1]);
        
        return getParent(source)==getParent(destination);
    }
    
    static void union(int a, int b){
        a = getParent(a);
        b = getParent(b);
        if(a<b) parent[b] = a;
        else parent[a] = b;
    }

    static int getParent(int x){
        if(parent[x]!=x)
            parent[x] = getParent(parent[x]);
        return parent[x];
    }
}

- 97%, 97%