Đọc ba dạng tệp dữ liệu đồ thị

|Tệp mẫu|Các dòng sau n| |---|---| |canh.inp|Mỗi dòng có hai chỉ số u v của một cạnh| |ma_tran.inp|Đúng n dòng, mỗi dòng n số 0/1 cách bằng khoảng trắng| |ke.inp|Đúng n dòng; dòng của u bắt đầu bằng u, rồi các đỉnh kề| Trong ke.inp, dòng `0 1 2` nói 0 kề với 1,2; dòng chỉ có `6` giữ thông tin đỉnh 6 biệt lập. Không xem số 0 đầu dòng là một đỉnh kề. Bộ mẫu dùng đơn đồ thị: không có khuyên, không lặp cạnh, chỉ số từ 0 đến n−1. Với cạnh vô hướng, tệp canh.inp ghi một lần; chương trình thêm cả hai chiều. Với cạnh có hướng, chỉ thêm chiều u→v.

from_edges trả Adj; danh sách các đỉnh có thể lấy bằng `list(range(len(Adj)))`. Mỗi hàng được sắp để các ví dụ duyệt có cùng quy ước xét đỉnh kề tăng dần. Lặp cạnh, khuyên hoặc chỉ số sai được báo lỗi, không âm thầm tạo đồ thị khác. ```python def from_edges(n, edges, directed=False): if n < 0: raise ValueError("Số đỉnh không hợp lệ") Adj = [[] for _ in range(n)] for u, v in edges: if not (0 <= u < n and 0 <= v < n) or u == v: raise ValueError("Cạnh không hợp lệ của đơn đồ thị") if v in Adj[u]: raise ValueError("Cạnh bị lặp") Adj[u].append(v) if not directed: Adj[v].append(u) for row in Adj: row.sort() return Adj ```

Các hàm có sẵn trong do_thi.py của bộ mẫu. read_matrix trả A, read_adj và read_edges trả Adj. Hai hàm đọc ma trận/danh sách kề giữ đúng dữ liệu đã ghi; khi dùng cho vô hướng, dữ liệu phải có cả hai chiều tương ứng. Nhập nhầm một dãy liền `0110000` vào tệp ma trận mẫu sẽ không được hiểu thành bảy cột vì chương trình dùng split. Cần viết `0 1 1 0 0 0 0` như khuôn dạng đã quy định. ```python def read_data(path): with open(path, encoding='utf-8') as f: n = int(f.readline()) lines = f.readlines() if n < 0: raise ValueError("Số đỉnh không hợp lệ") return n, lines def read_edges(path, directed=False): n, lines = read_data(path) edges = [tuple(map(int, line.split())) for line in lines if line.strip()] return from_edges(n, edges, directed) def read_matrix(path): n, lines = read_data(path) A = [list(map(int, line.split())) for line in lines] if len(A) != n or any(len(row) != n for row in A): raise ValueError("Ma trận phải có n hàng, n cột") if any(x not in (0, 1) for row in A for x in row): raise ValueError("Ma trận kề chỉ nhận 0 hoặc 1") if any(A[u][u] != 0 for u in range(n)): raise ValueError("Đơn đồ thị không có khuyên") return A def read_adj(path): n, lines = read_data(path) if len(lines) != n: raise ValueError("Danh sách kề phải có n dòng") Adj = [] for u, line in enumerate(lines): row = list(map(int, line.split())) if not row or row[0] != u: raise ValueError("Sai nhãn đầu dòng") neighbors = row[1:] if any(not 0 <= v < n or v == u for v in neighbors): raise ValueError("Đỉnh kề không hợp lệ") if len(set(neighbors)) != len(neighbors): raise ValueError("Đỉnh kề bị lặp") Adj.append(neighbors) return Adj ```