from collections import defaultdict, deque
def minInitialVertices(matrix):
m, n = len(matrix), len(matrix[0])
graph = defaultdict(list)
in_degree = [[0] * n for _ in range(m)]
# Create directed edges and calculate in-degrees
for i in range(m):
for j in range(n):
if i > 0 and matrix<i>[j] >= matrix[i-1][j]:
graph[(i-1, j)].append((i, j))
in_degree<i>[j] += 1
if j > 0 and matrix<i>[j] >= matrix<i>[j-1]:
graph[(i, j-1)].append((i, j))
in_degree<i>[j] += 1
# Perform topological sort
queue = deque()
for i in range(m):
for j in range(n):
if in_degree<i>[j] == 0:
queue.append((i, j))
result = []
while queue:
x, y = queue.popleft()
result.append((x, y))
for neighbor in graph[(x, y)]:
in_degree[neighbor[0]][neighbor[1]] -= 1
if in_degree[neighbor[0]][neighbor[1]] == 0:
queue.append(neighbor)
# Return minimum initial vertices
return result
# Example usage
matrix = [[7, 5, 2],
[2, 4, 3],
[6, 5, 8]]
vertices = minInitialVertices(matrix)
print(vertices)
# Example usage
matrix = [[7, 5, 2],
[2, 4, 3],
[6, 5, 8]]
vertices = minInitialVertices(matrix)
print(vertices)
|