Kiểm tra đường đi trong đồ thị vô hướng (Find if Path Exists)

Cho đồ thị vô hướng gồm n đỉnh đánh số từ 0 đến n - 1 và danh sách cạnh edges. Cho đỉnh xuất phát source và đích destination. Hãy xác định xem có tồn tại đường đi hợp lệ giữa hai đỉnh này hay không.

Ví dụ 1:

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

Ví dụ 2:

Input:
n = 6
edges = [[0,1],[0,2],[3,5],[5,4],[4,3]]
source = 0
destination = 5
Output: false

Định Dạng Đầu Vào (Input)

Dòng 1: Số nguyên n
Dòng 2: Mảng edges
Dòng 3: source
Dòng 4: destination

Định Dạng Đầu Ra (Output)

true hoặc false

Ràng Buộc (Constraints)

1 <= n <= 2 * 10^5

Ví Dụ Kiểm Thử Mẫu

Ví dụ 1:

Input:

3
[[0,1],[1,2],[2,0]]
0
2

Output:

true

Giải thích: Có đường đi 0 -> 2

Ví dụ 2:

Input:

6
[[0,1],[0,2],[3,5],[5,4],[4,3]]
0
5

Output:

false

Giải thích: Đồ thị rời rạc

Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.

Kỹ thuật BFS / DFS hoặc Union-Find O(V + E)

Duyệt từ source bằng hàng đợi BFS, nếu chạm đích destination thì trả về true.

Vui lòng đăng nhập

Đăng nhập tài khoản học viên để xem lịch sử nộp bài của bạn.

Đăng nhập