Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

code báo không có thư viện numpy import numpy as np def inputdata(): with…

  1. User

    code báo không có thư viện numpy import numpy as np

    def input_data(): with open("color1.txt", "r") as f: n = int(f.readline()) graph = [] for i in range(n): graph.append(list(map(int, f.readline().split()))) return n, np.array(graph)

    def degree(graph, u): return np.sum(graph[u,:])

    def find_max_dsatur(graph, color, colored, saturation): max_saturation = -1 max_dsatur = -1 for i in range(graph.shape[0]): if color[i] == -1: saturation[i] = 0 for j in range(graph.shape[0]): if graph[i,j] == 1 and color[j] != -1: colored[int(color[j])] += 1 for j in range(graph.shape[0]): if graph[i,j] == 1 and color[j] == -1: saturation[i] += 1 if saturation[i] > max_saturation or (saturation[i] == max_saturation and degree(graph, i) > degree(graph, max_dsatur)): max_saturation = saturation[i] max_dsatur = i for j in range(graph.shape[0]): if graph[i,j] == 1 and color[j] != -1: colored[int(color[j])] -= 1 return max_dsatur

    def dsatur(graph): color = np.full(graph.shape[0], -1) colored = np.zeros(graph.shape[0], dtype=int) saturation = np.zeros(graph.shape[0], dtype=int) max_dsatur = np.argmax([degree(graph, i) for i in range(graph.shape[0])]) color[max_dsatur] = 0 count = 1 while count < graph.shape[0]: u = find_max_dsatur(graph, color, colored, saturation) available = np.where(colored == 0)[0] k = len(available) if k == 0: color[u] = count count += 1 else: idx = available[0] for i in range(1, k): if degree(graph, available[i]) > degree(graph, idx): idx = available[i] color[u] = idx colored[color[u]] = 1 return color

    def output_data(color): print("Total colors:", np.amax(color) + 1) for i, c in enumerate(color): print("Node", i, "-", "Color:", c + 1)

    if name == "main": n, graph = input_data() color = dsatur(graph) output_data(color)

  2. Assistant

    Code sau đây là mã của thuật toán DSATUR để giải quyết bài toán tô màu đồ thị. Mã không có thư viện numpy:

    def input_data():
       with open("color1.txt", "r") as f:
            n = int(f.readline())
            graph = []
            for i in range(n):
                graph.append(list(map(int, f.readline().split())))
            return n, graph
    
    def degree(graph, u):
        deg = 0
        for i in range(len(graph)):
            if graph[i][u] == 1:
                deg += 1
        return deg
    
    def find_max_dsatur(graph, color, colored, saturation):
        max_saturation = -1
        max_dsatur = -1
        for i in range(len(graph)):
            if color[i] == -1:
                saturation[i] = 0
                for j in range(len(graph)):
                    if graph[i][j] == 1 and color[j] != -1:
                        colored[color[j]] += 1
                for j in range(len(graph)):
                    if graph[i][j] == 1 and color[j] == -1:
                        saturation[i] += 1
                if saturation[i] > max_saturation or (saturation[i] == max_saturation and degree(graph, i) > degree(graph, max_dsatur)):
                    max_saturation = saturation[i]
                    max_dsatur = i
                for j in range(len(graph)):
                    if graph[i][j] == 1 and color[j] != -1:
                        colored[color[j]] -= 1
        return max_dsatur
    
    def dsatur(graph):
        color = [-1] * len(graph)
        colored = [0] * len(graph)
        saturation = [0] * len(graph)
        max_dsatur = max(range(len(graph)), key=lambda i: degree(graph, i))
        color[max_dsatur] = 0
        count = 1
        while count < len(graph):
            u = find_max_dsatur(graph, color, colored, saturation)
            available = [i for i in range(len(colored)) if colored[i] == 0]
            k = len(available)
            if k == 0:
                color[u] = count
                count += 1
            else:
                idx = available[0]
                for i in range(1, k):
                    if degree(graph, available[i]) > degree(graph, idx):
                        idx = available[i]
                color[u] = idx
            colored[color[u]] = 1
        return color
    
    def output_data(color):
        print("Total colors:", max(color) + 1)
        for i, c in enumerate(color):
            print("Node", i, "-", "Color:", c + 1)
    
    if __name__ == "__main__":
        n, graph = input_data()
        color = dsatur(graph)
        output_data(color)
    

    Lưu ý: Chương trình cần phải có file đầu vào "color1.txt" theo định dạng:

    n
    a_{11} a_{12} ... a_{n1}
    a_{21} a_{22} ... a_{n2}
    ...
    a_{n1} a_{n2} ... a_{nn}
    

    trong đó, n là số đỉnh của đồ thị, a_{ij} là trọng số của cạnh nối từ đỉnh i đến đỉnh j. Nếu a_{ij} = 1 thì có cạnh nối trực tiếp từ đỉnh i đến đỉnh j, ngược lại thì không có cạnh nối trực tiếp giữa hai đỉnh này.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.