Mạng lưới liên thông
Points
12
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề 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
YESnếu đồ thị liên thông, ngược lại in raNO.
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$.
Community Discussion