Mạng lưới liên thông

Buổi 18 — BFS & DFS
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kỳ luôn tồn tại đường đi nối chúng. Hãy kiểm tra xem đồ thị đã cho có liên thông hay không.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
  • In ra YES nếu đồ thị liên thông, ngược lại in ra NO.
Ví dụ
Input Output
4 3
1 2
2 3
3 4
YES
4 2
1 2
3 4
NO
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Draft saved