Viết chương trình đếm số nước liên minh với nước đã cho Yêu cầu: Có N nước, các nước được chia thành các liên minh. Quan hệ liên minh như sau...

Để giải quyết bài toán này, chúng ta sẽ sử dụng thuật toán duyệt đồ thị theo chiều rộng (BFS - Breadth-First Search). Thuật toán này sẽ giúp chúng ta xác định số lượng nước liên minh với nước X từ dữ liệu đã cho.

Các bước giải quyết bài toán:

1. Đọc dữ liệu từ file: Đọc danh sách các nước và các liên minh từ tệp lienminh.txt. Hàng đầu tiên là danh sách các nước, các hàng tiếp theo là các cặp nước liên minh, và hàng cuối cùng là nước X cần xác định số nước liên minh.

2. Biểu diễn đồ thị: Sử dụng một danh sách kề để lưu trữ các nước liên minh với nhau.

3. Duyệt đồ thị bằng BFS: Bắt đầu từ nước X, sử dụng BFS để duyệt qua tất cả các nước liên minh và đếm số lượng nước liên minh này.

4. Xuất kết quả: In ra số lượng nước liên minh với nước X.

Dưới đây là mã Python để giải quyết bài toán:

from collections import defaultdict, deque

def read_graph_data(filename):

   adjacency_list = defaultdict(list)

    start_node = None

    with open(filename, 'r') as f:

        lines = f.readlines()

       countries = lines[0].strip().split()

        for line in lines[1:]:

            if line.strip() == '':

               continue

           node1, node2 = line.strip().split()

            if start_node is None:

               start_node = node1

           adjacency_list[node1].append(node2)

           adjacency_list[node2].append(node1)

       x_country = lines[-1].strip()

    return countries, adjacency_list, x_country

def bfs_count_connected(adjacency_list, start_node):

    visited = set()

    queue = deque([start_node])

   visited.add(start_node)

    count = 0

    while queue:

        node = queue.popleft()

        count += 1

        for neighbor in adjacency_list[node]:

            if neighbor not in visited:

               visited.add(neighbor)

               queue.append(neighbor)

    return count

def main():

    filename = 'lienminh.txt'

    countries, adjacency_list, x_country = read_graph_data(filename)

    if x_country not in adjacency_list:

       print(f"Nước {x_country} không có trong danh sách các nước liên minh.")

        return

   num_connected_countries = bfs_count_connected(adjacency_list, x_country)

   print(f"Số nước liên minh với nước {x_country} là: {num_connected_countries}")

if __name__ == "__main__":

    main()

Giải thích mã giả:

• read_graph_data(filename): Đọc dữ liệu từ tệp filename, xây dựng danh sách các nước và danh sách kề (adjacency list) biểu diễn các liên minh giữa các nước. Trả về danh sách các nước, danh sách kề và nước X cần tìm.

• bfs_count_connected(adjacency_list, start_node): Sử dụng BFS để đếm số lượng nước liên minh với start_node trong đồ thị biểu diễn bởi adjacency_list.

• main(): Hàm chính thực hiện đọc dữ liệu từ tệp lienminh.txt, xây dựng đồ thị và tính toán số lượng nước liên minh với nước X, sau đó in ra kết quả.