DFS cơ bản
Xem PDFĐồ 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
7 6
1 2
1 3
2 3
5 6
6 7
5 7 Output
3
Bình luận
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
if name == "main":
main() PY3 ĐÂY
3 bình luận nữa