Appearance
question:In a kingdom far away, there are N towns connected by M bidirectional roads. The kingdom's ruler wants to ensure that the kingdom is well-connected, and that for any two towns, there is at most one unique path connecting them. - Each town is uniquely identified by an integer from 1 to N. - Each road directly connects two towns and has a certain travel cost associated with it. However, due to growing concerns about the kingdom's security, the ruler wants to remove some roads while still ensuring that the condition of at most one unique path between any two towns is maintained (i.e., ensuring the resulting structure is a tree). The ruler wants to minimize the total travel cost of the remaining roads. Your task is to help the ruler determine the minimum total travel cost of the roads that need to be retained. -----Input----- The first line contains two integers N and M, the number of towns and roads, respectively. The next M lines each contain three integers u, v, and w, describing a road between towns u and v with a travel cost of w. -----Output----- Output a single integer, the minimum total travel cost of the roads that need to be retained in order to ensure there is at most one unique path between any two towns. -----Constraints----- - 1 ≤ N ≤ 1000 - 1 ≤ M ≤ 100000 - 1 ≤ u, v ≤ N - 1 ≤ w ≤ 1000 -----Example----- Input: 5 6 1 2 3 1 3 1 3 4 2 3 5 4 4 5 5 2 4 6 Output: 10 -----Explanation----- The minimum total travel cost comes from retaining the roads: (1-3), (3-4), (1-2), and (3-5). This forms a spanning tree with the minimum total travel cost of 10.
answer:def find(parent, i): if parent[i] == i: return i else: return find(parent, parent[i]) def union(parent, rank, x, y): root_x = find(parent, x) root_y = find(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 def kruskal_min_spanning_tree(N, roads): roads.sort(key=lambda x: x[2]) parent = [] rank = [] for node in range(N+1): parent.append(node) rank.append(0) min_cost = 0 num_edges = 0 for road in roads: u, v, w = road root_u = find(parent, u) root_v = find(parent, v) if root_u != root_v: min_cost += w num_edges += 1 union(parent, rank, root_u, root_v) if num_edges == N - 1: break return min_cost def minimum_total_travel_cost(N, M, roads): return kruskal_min_spanning_tree(N, roads)
question:# Task Given an array of integers, your task is to rearrange its elements such that all zeros are moved to the end of the array while maintaining the relative order of the non-zero elements. You need to do this in place, and the relative order of the non-zero elements should be preserved. Write a function `move_zeros(arr)` that takes as input an array of integers `arr` and modifies it to move all zeros to the end. **Constraints:** - The length of `arr` (denoted as `n`) will be between `1` and `10^5`. - The values in `arr` can be any integer, including negative values. **Example:** ```python def move_zeros(arr): # Your code here arr = [0, 1, 0, 3, 12] move_zeros(arr) print(arr) # Outputs: [1, 3, 12, 0, 0] ``` For `arr = [1, 0, 2, 0, 4]`, after calling `move_zeros(arr)`, the array should be modified to `[1, 2, 4, 0, 0]`. For `arr = [0, 0, 1, 0, 2]`, after calling `move_zeros(arr)`, the array should be modified to `[1, 2, 0, 0, 0]`. **Note:** - You must perform the operation in place without using additional space for another array. - Do not return anything from your function. The array should be modified directly.
answer:def move_zeros(arr): Moves all zeros in the array to the end while maintaining the relative order of the non-zero elements. non_zero_index = 0 # Index to place the next non-zero element # Traverse the array and move all non-zero elements to the beginning for i in range(len(arr)): if arr[i] != 0: arr[non_zero_index] = arr[i] non_zero_index += 1 # Fill the remaining elements with zeroes for i in range(non_zero_index, len(arr)): arr[i] = 0
question:You are given an undirected graph with N nodes and M edges. Each edge connects two different nodes and has a positive integer weight. Your task is to compute the sum of the weights of the edges in the Minimum Spanning Tree (MST) of this graph. -----Input:----- - First line will contain two integers N and M. - Each of the next M lines will contain three integers u, v, and w, representing an edge between nodes u and v with weight w. -----Output:----- Print the sum of the weights of the edges in the MST. -----Constraints----- - 1 leq N leq 1000 - 1 leq M leq 200000 - 1 leq u, v leq N - 1 leq w leq 1000000 -----Sample Input:----- 4 5 1 2 3 2 3 4 3 4 5 4 1 2 1 3 6 -----Sample Output:----- 9
answer:def find(parent, i): if parent[i] == i: return i else: parent[i] = find(parent, parent[i]) return parent[i] def union(parent, rank, x, y): rootX = find(parent, x) rootY = find(parent, y) if rootX != rootY: if rank[rootX] > rank[rootY]: parent[rootY] = rootX elif rank[rootX] < rank[rootY]: parent[rootX] = rootY else: parent[rootY] = rootX rank[rootX] += 1 def kruskal(n, edges): parent = list(range(n)) rank = [0] * n edges.sort(key=lambda edge: edge[2]) mst_weight = 0 for u, v, w in edges: rootU = find(parent, u) rootV = find(parent, v) if rootU != rootV: union(parent, rank, rootU, rootV) mst_weight += w return mst_weight def minimum_spanning_tree(n, m, edges): edges = [(u-1, v-1, w) for u, v, w in edges] return kruskal(n, edges) # Sample input for testing n, m = 4, 5 edges = [ (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 1, 2), (1, 3, 6) ] print(minimum_spanning_tree(n, m, edges)) # Should output 9
question:Given a grid, where some cells are walkable and others are obstacles, determine the shortest path from the top-left corner to the bottom-right corner. The grid is represented as a 2D array where a 0 represents a walkable cell and a 1 represents an obstacle. Write a function `shortest_path(grid)` that calculates the minimum number of steps required to get from the top-left to the bottom-right corner. If it is not possible to reach the destination, return -1. The function should consider the following: - You can move up, down, left, or right from a cell. - The input grid will always have at least 1 row and 1 column. # Examples: ``` shortest_path([ [0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 1, 0], [0, 0, 0, 0] ]) # Returns 5 (the path is (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,1) -> (3,2) -> (3,3)) shortest_path([ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]) # Returns 4 (the path is (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)) shortest_path([ [0, 1], [1, 0] ]) # Returns -1 (there is no valid path from the top-left to the bottom-right) ```
answer:from collections import deque def shortest_path(grid): if not grid or grid[0][0] == 1: return -1 rows, cols = len(grid), len(grid[0]) queue = deque([(0, 0, 0)]) # row, column, steps visited = set((0, 0)) while queue: r, c, steps = queue.popleft() if r == rows - 1 and c == cols - 1: return steps for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)): # right, down, left, up nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr, nc) not in visited: queue.append((nr, nc, steps + 1)) visited.add((nr, nc)) return -1