Thành phần liên thông và chu trình vô hướng

Với **đồ thị vô hướng**, mỗi lượt DFS từ một đỉnh chưa thăm thu một thành phần liên thông. Mẫu có hai nhóm: [0,1,3,5,4,2] và [6]. Thứ tự trong nhóm là thứ tự duyệt; thành phần được xác định bởi tập đỉnh, không phải vị trí ghi trong danh sách. Nếu chỉ có một nhóm và n>0, đồ thị liên thông. Nếu có hai nhóm, lấy một đỉnh ở mỗi nhóm sẽ cho một cặp không thể đi tới nhau. Không dùng số lần bắt đầu DFS theo cách này để gọi đó là số thành phần liên thông mạnh của đồ thị có hướng.

Ở đồ thị vô hướng, đi từ u tới v thì hàng Adj[v] có u. Cạnh ngược về cha là cùng một cạnh đang được nhìn từ đầu kia, chưa là chu trình. Khi BFS từ u gặp v đã thăm, chỉ kết luận chu trình nếu v khác prev[u]. Mã phải kiểm các vùng chưa tới được nữa, không chỉ vùng chứa đỉnh 0. Các hàm dưới đây chỉ dùng cho danh sách kề **đơn đồ thị vô hướng hợp lệ**, có đủ hai chiều và không cạnh trùng. ```python def components(Adj): seen = [False]*len(Adj) groups = [] for u in range(len(Adj)): if not seen[u]: group = [] dfs_visit(Adj, u, seen, group) groups.append(group) return groups def undirected_cycle(Adj): n = len(Adj) seen = [False]*n prev = [None]*n for s in range(n): if seen[s]: continue Q = [s] head = 0 seen[s] = True while head < len(Q): u = Q[head] head += 1 for v in Adj[u]: if not seen[v]: seen[v] = True prev[v] = u Q.append(v) elif v != prev[u]: return True return False ```

Tải và giải nén toàn bộ ZIP, giữ các tệp cùng thư mục. Cần Python 3, không có thư viện cài thêm. Mở demo.py để xem đối chiếu dữ liệu, DFS/BFS, đường đi, thành phần liên thông và chu trình. Mở xe_dap.py để nhập hai chỉ số theo bài trước. Tệp do_thi.py chứa các hàm trong bài. canh.inp, ma_tran.inp, ke.inp mô tả cùng đồ thị; tien_quyet.inp dùng cạnh có hướng và ten_nha.inp lưu nhãn giả định. HUONG_DAN.txt ghi cách chạy, quy ước và kết quả đối chiếu. Thực hành trên bản sao với đồ thị nhỏ. Giữ đúng n, phạm vi chỉ số và định dạng từng tệp. Để thử liên thông, thêm cạnh 5–6 ở bản sao canh.inp: mọi đỉnh sẽ tới được từ 0, 6 ở khoảng cách 4. Để thử đồ thị vô hướng không chu trình, dùng chuỗi 0–1–2; cạnh đi ngược về cha không được báo thành chu trình. So kết quả in với sơ đồ và bảng truy vết. Câu luyện kiểm hiểu thứ tự, điều kiện và kết quả; chọn đáp án chưa chứng minh đã tự chạy chương trình.