Explore with a pile instead of recursion
Replace the function calls with your own pile of places to visit, and total up whole connected groups. About 14 minutes.
A pile of places to visit
So far the search used function calls, which wait for each other like a stack of paused tasks. You can do the same by hand with a pile. Put the start on the pile. Then repeat: take the top place off, handle it, and put its unseen neighbours on the pile.
The result is the same depth-first exploration, and there is no limit on depth from the program's call stack, which matters for very long chains.
One search for each network
Suppose each person in a set of friendship circles holds some coins, and you want the richest circle. A search from one person reaches exactly their circle, so add up the coins as you visit.
When the pile is empty, that circle is done. Look for the next person you haven't seen: they must be in a different circle, so start a new search there. Keep the largest total you find.
n = len(values)
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
seen = [False] * n
best = 0
for start in range(n):
if seen[start]:
continue
seen[start] = True
stack, total = [start], 0
while stack:
node = stack.pop()
total += values[node]
for nxt in adj[node]:
if not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
best = max(best, total)
return bestSix people hold 5, 3, 4, 10, 1 and 7 coins. We want the richest circle of connected friends.
The search has finished one circle and the pile is empty. There are still places without a mark. What next?
- AStart a fresh search from one of them
- BStop: the search is complete
- CClear all the marks and begin again
Show the answer
Start a fresh search from one of them. An unmarked place is in a different circle, so a new search covers it.
The richest network
There are n people, numbered 0 to n − 1, where person i holds values[i] coins. edges[i] = [a, b] means persons a and b are friends (in both directions). A circle is a group of people who are connected through friends. Return the largest total number of coins held by any one circle.
values = [5, 3, 4, 10, 1, 7], edges = [[0, 1], [1, 2], [3, 4]] → 12
1 ≤ n ≤ 500 · 0 ≤ values[i] ≤ 1,000 · 0 ≤ friendships ≤ 5,000