Silnie spójne składowe skierowane
Podziel graf skierowany do 64 wierzchołków na silnie spójne składowe.
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)
Sprawdź przed zastosowaniem
Porównaj rzeczywiste zachowanie z oczekiwanym wynikiem. Jeśli sprawdzenie się nie powiedzie, wyjaśnij przyczynę przed kolejnymi zmianami.
Modele
Dodaj endpoint zgodny z OpenAI lub Anthropic, podając bazowy URL i klucz API, jeśli jest wymagany. Sprawdź połączenie. Lokalny serwer modelu musi działać; zdalne narzędzia mogą przesyłać dane oddzielnie.
Projekt
Sprawdź cykle, odizolowane wierzchołki i pusty przypadek, odrzucając błędne elementy bez zmiany zbiorów sąsiedztwa.
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)
Nadaj grupom zależności znaczenie użyteczne dla aplikacji
ComponentWisp to środowisko programowania z AI dla Windows dla programistów śledzących relacje w danych i kodzie projektu. Dodaj do rozmowy reprezentację grafu i kod odbierający, który potrzebuje jego grup. Poproś asystenta o sprawdzenie znaczenia krawędzi skierowanej przed zaproponowaniem zmiany grupowania. Wynik jest użyteczny tylko wtedy, gdy zachowane relacje odpowiadają pytaniu, na które aplikacja próbuje odpowiedzieć.
Zadanie wokół strong_components.py może dotyczyć grup, których wierzchołki są wzajemnie osiągalne ścieżkami skierowanymi. Użyj małego przykładu zależności, aby odróżnić wzajemną osiągalność od połączenia jednokierunkowego, a następnie oceń implementację i kolejność wyników. Jeśli stosujesz kod do zależności, jawnie określ mapowanie rzeczywistych obiektów na wierzchołki; sama funkcja pomocnicza nie może ustalić znaczenia tych zależności.
Po przeczytaniu propozycji uruchom kontrole projektu z cyklem, połączeniem jednokierunkowym i izolowanymi wierzchołkami. Sprawdź kod odbierający, aby potwierdzić spójne traktowanie wynikowych grup. ComponentWisp łączy się z obsługiwanymi punktami końcowymi zgodnymi z OpenAI lub Anthropic, z danymi uwierzytelniającymi w razie potrzeby. Modele bez ograniczeń można wybrać tam, gdzie są oferowane, a model i serwer określają ograniczenia, narzędzia i limity kontekstu. Zachowaj znaczenie krawędzi i oczekiwane grupy w rozmowie, aby kolejne zmiany utrzymywały to samo wymaganie oprogramowania.
Pytania o kod grupowania zależności
Czy jednokierunkowa zależność wystarcza do połączenia obiektów w grupę?
Nie dla grupy zdefiniowanej wzajemną osiągalnością skierowaną. Określ zamierzoną regułę grupowania i dołącz przykład jednokierunkowy, aby proponowana implementacja nie traktowała przypadkowo relacji skierowanej jak połączenia nieskierowanego.
Jak mapować rzeczywiste obiekty projektu na wierzchołki?
Zachowaj jawne mapowanie, którego kod odbierający może używać do interpretacji wyników. Sprawdź skutki usunięcia lub zmiany kolejności obiektów i przetestuj, czy zwrócone grupy nadal odnoszą się do właściwych obiektów projektu.
Czy grupowanie zależności określa kolejność wykonania?
Odpowiada na inne pytanie. Aplikacja może potrzebować dodatkowej logiki porządkowania grup lub obsługi cykli. Określ to wymaganie oddzielnie i sprawdź odpowiedni kod odbierający, zamiast zakładać, że podział jest kompletnym planem wykonania.
Dlaczego uwzględniać izolowane wierzchołki w kontrolach?
Potwierdzają, że obiekty bez krawędzi nadal otrzymują reprezentację oczekiwaną przez aplikację. Sprawdź wynik funkcji pomocniczej i widok odbiorcy, zwłaszcza jeśli refaktoryzacja buduje struktury pośrednie przez iterację wyłącznie po istniejących połączeniach.
ComponentWisp · Zaktualizowano 2026-10-25