Завантажте застосунок
Виберіть папку й попросіть помічника прочитати потрібні файли перед редагуванням. Визначте мету та межі завдання.
Сценарії
Сценарії роботи з кодом · Сильні компоненти орієнтованого графа
03
Сценарії
Розбийте орієнтований граф до 64 вершин на сильні компоненти. Перевірте цикли, окремі вершини й порожній граф, відхиляючи хибні елементи без зміни множин суміжності.
Відкрийте папку проєкту
Оберіть сумісний endpoint. Доступність інструментів і якість відповідей залежать від налаштованої моделі та сервера.
Підключіть і перевірте модель
Переглядайте зміни й результати команд. Перед прийняттям результату виконайте перевірки проєкту; створений код не тестується автоматично.
Перегляньте зміни та запустіть тести
Порівняйте фактичну поведінку з очікуваним результатом. Якщо перевірка не проходить, з’ясуйте причину перед наступними змінами.
Сильні компоненти орієнтованого графа
Сценарії
def strong_components(graph):
if type(graph) is not list or len(graph) > 64:
raise ValueError("scc.graph")
n = len(graph)
if any(type(row) is not set or any(type(v) is not int or not 0 <= v < n for v in row) for row in graph):
raise ValueError("scc.edge")
seen, order = set(), []
for start in range(n):
if start in seen:
continue
seen.add(start)
stack = [(start, iter(sorted(graph[start])))]
while stack:
node, edges = stack[-1]
target = next(edges, None)
if target is None:
order.append(node)
stack.pop()
elif target not in seen:
seen.add(target)
stack.append((target, iter(sorted(graph[target]))))
reverse = [set() for _ in graph]
for node, edges in enumerate(graph):
for target in edges:
reverse[target].add(node)
seen, result = set(), []
for start in reversed(order):
if start in seen:
continue
group, pending = [], [start]
seen.add(start)
while pending:
node = pending.pop()
group.append(node)
for target in reverse[node]-seen:
seen.add(target)
pending.append(target)
result.append(sorted(group))
return sorted(result)
Перевірте перед застосуванням. Переглядайте зміни й результати команд. Перед прийняттям результату виконайте перевірки проєкту; створений код не тестується автоматично.