Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- Math
- array
- two pointers
- simulation
- hash table
- bit manipulation
- 파이썬
- 자바
- Tree
- database
- string
- 코딩테스트
- 구현
- Number Theory
- sorting
- Matrix
- Binary Tree
- Stack
- Method
- Data Structure
- java
- 코테
- geometry
- Counting
- implement
- greedy
- Class
- dynamic programming
- SQL
- Binary Search
Archives
- Today
- Total
코린이의 소소한 공부노트
[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%