code báo không có thư viện numpy import numpy as np def inputdata(): with…
- 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)
- 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 đó,
nlà số đỉnh của đồ thị,a_{ij}là trọng số của cạnh nối từ đỉnhiđến đỉnhj. Nếua_{ij} = 1thì có cạnh nối trực tiếp từ đỉnhiđến đỉnhj, ngược lại thì không có cạnh nối trực tiếp giữa hai đỉnh này.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.