DFS cơ bản

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đồ thị: Gồm một tập các đỉnh được nối với nhau bằng các cạnh. Nếu không không được chỉ rõ trong ngữ cảnh, đồ thị được hiểu là đồ thị đơn.

Liên thông: Nếu giữa hai điểm bất kỳ của một đồ thị đều có thể thiết lập một đường đi từ đỉnh này đến đỉnh kia, đồ thị được coi là liên thông; nếu không, đồ thị được coi là không liên thông. Một đồ thị được coi là hoàn toàn không liên thông nếu không có đường đi giữa hai đỉnh bất kỳ trong đồ thị. Đây chỉ là một cái tên khác để miêu tả một đồ thị rỗng hoặc một tập độc lập.

Yêu cầu: Cho đơn đồ thị vô hướng $G = (V, E)$ gồm $n$ đỉnh và $m$ cạnh, các đỉnh được đánh số từ $1$ tới $n$ và các cạnh được đánh số từ $1$ tới $m$. Tìm số thành phần liên thông của đồ thị.

Input

Dòng 1: Chứa hai số $n, m$.
$M$ dòng tiếp theo: Dòng thứ $i$ có dạng 2 số nguyên $u, v$. Trong đó $u, v$ là chỉ số hai đỉnh đầu mút của cạnh thứ $i$.

Output

Ghi số $k$ là số thành phần liên thông của đồ thị.

Constraints

$1 \leq n \leq 100000$
$1 \leq m \leq 100000$

Example

Test 1

Input

Output

Bình luận

0
hjhjhjhjhj 3:13 p.m. 5 Tháng 4, 2024
from collections import deque

def bfs(graph, v, visited):
visited[v] = True
queue = deque([v])
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)

def count_connected_components(graph):
n = len(graph)
visited = [False] * n
count = 0
for v in range(n):
if not visited[v]:
count += 1
bfs(graph, v, visited)
return count

def main():
n, m = map(int, input().split()) # Đọc số lượng đỉnh và cạnh
graph = [[] for _ in range(n)] # Tạo danh sách kề cho mỗi đỉnh
for _ in range(m):
u, v = map(int, input().split()) # Đọc các cạnh
graph[u - 1].append(v - 1) # Thêm cạnh u-v vào danh sách kề
graph[v - 1].append(u - 1) # Vì đồ thị vô hướng nên cần thêm cả u-v và v-u

# Gọi hàm để đếm số thành phần liên thông và in ra kết quả print(count_connected_components(graph))

if name == "main":
main() PY3 ĐÂY

0

ducmanhhb15 1:11 p.m. 27 Tháng 7, 2023

Dùng python có ăn full đc test k mng @@ mình k ăn full được 🙁

1

nvhoang 6:36 p.m. 22 Tháng 11, 2022

Cho em xin bộ 45 test của bài này với ạ

6
jumptozero 10:25 a.m. 30 Tháng 5, 2021
Mình xin chia sẻ lời giải bài này như sau:

Bước 1: Đọc dữ liệu và đưa về danh sách đỉnh kề tương tự bài BFS Cơ bản

Bước 2: Ta sẽ duyệt qua tất cả các đỉnh của đồ thị và kiểm tra rằng, đỉnh $i$ nào đó đã thuộc về một đồ thị liên thông nào chưa ? Nếu chưa thì ta sử dụng hàm DFS để gôm tất cả những đỉnh có thể đến $i$ về thành một đồ thị liên thông ! Và ở đây ta sử dụng một biến $dem$ để đếm số lượng thành phần liên thông .

Và ở đây mình sử dụng mảng $dau[]$ để đánh dấu đỉnh $i$ đã thuộc về một đồ thị liên thông nào chưa ?

Ban đầu, tất cả các phần tử của mảng $dau[]$ đều bằng $0$

Cụ thể các bạn có thể xem hình ảnh dưới đây:

Như vậy là bài toán đã giải quyết xong

Bước 3: ** Triển khai hàm $DFS()$. Về bản chất hàm $DFS$ tương tự hàm $BFS$ nhưng chỉ khác cấu trúc dữ liệu đó là ở $BFS$ ta sử dụng **queue thì ở $DFS$ ta sử dụng stack. Ở đây, mình sẽ chia sẻ $2$ lệnh cơ bản của stack đó là :

$p=st.top()$: Có nghĩa là lấy phần tử trên cùng của stack

$st.pop()$: Loại bỏ phần tử trên cùng của stack

Để dễ hình dung, các bạn có thể xem ảnh ở dưới đây !

\[$ void dfs(ll source) { dau[source] = 1; stack<ll> st; st.push(source); while (!st.empty()) { ll p = st.top(); st.pop(); for (auto v : edges[p]) { if (dau[v] == 1) continue; dau[v] = 1; st.push(v); } } } $\]

Ps:

Ở đây, chúng ta có thể sử dụng BFS thay cho DFS

Các bạn có thể tham khảo code mình tại đây

Nếu có gì khó hiểu, các bạn comment nhé !