Find circular gift exchange chains

# Table: SecretSanta
#
# +-------------+------+
# | Column Name | Type |
# +-------------+------+
# | giver_id    | int  |
# | receiver_id | int  |
# | gift_value  | int  |
# +-------------+------+
# (giver_id, receiver_id) is the unique key for this table.
# Each row represents a record of a gift exchange between two employees, giver_id represents the employee who gives a gift, receiver_id represents the employee who receives the gift and gift_value represents the value of the gift given.
#
# Write a solution to find the total gift value and length of circular chains of Secret Santa gift exchanges:
#
# A circular chain is defined as a series of exchanges where:
#
# Each employee gives a gift to exactly one other employee.
#
# Each employee receives a gift from exactly one other employee.
#
# The exchanges form a continuous loop (e.g., employee A gives a gift to B, B gives to C, and C gives back to A).
#
# Return the result ordered by the chain length and total gift value of the chain in descending order.
#
# The result format is in the following example.
#
# Example 1:
# Input:
# SecretSanta table:
# +----------+-------------+------------+
# | giver_id | receiver_id | gift_value |
# +----------+-------------+------------+
# | 1        | 2           | 20         |
# | 2        | 3           | 30         |
# | 3        | 1           | 40         |
# | 4        | 5           | 25         |
# | 5        | 4           | 35         |
# +----------+-------------+------------+
# Output:
# +----------+--------------+------------------+
# | chain_id | chain_length | total_gift_value |
# +----------+--------------+------------------+
# | 1        | 3            | 90               |
# | 2        | 2            | 60               |
# +----------+--------------+------------------+
# Explanation:
# Chain 1 involves employees 1, 2, and 3:
# Employee 1 gives a gift to 2, employee 2 gives a gift to 3, and employee 3 gives a gift to 1.
# Total gift value for this chain = 20 + 30 + 40 = 90.
# Chain 2 involves employees 4 and 5:
# Employee 4 gives a gift to 5, and employee 5 gives a gift to 4.
# Total gift value for this chain = 25 + 35 = 60.
# The result table is ordered by the chain length and total gift value of the chain in descending order.

import pandas as pd


def find_gift_chains(secret_santa: pd.DataFrame) -> pd.DataFrame:
  if secret_santa.empty:
    return pd.DataFrame(columns=["chain_id", "chain_length", "total_gift_value"])

  # Build directed graph: giver -> receiver (each giver gives to exactly one person)
  next_node = dict(zip(secret_santa["giver_id"], secret_santa["receiver_id"]))
  gift_map = dict(
    zip(
      zip(secret_santa["giver_id"], secret_santa["receiver_id"]),
      secret_santa["gift_value"],
    )
  )

  visited = set()
  chains = []

  for start in next_node:
    if start in visited:
      continue

    path = []
    path_index = {}  # node -> index in path
    current = start

    while current not in visited and current not in path_index:
      path_index[current] = len(path)
      path.append(current)
      nxt = next_node.get(current)
      if nxt is None:
        current = None  # dead end
        break
      current = nxt

    if current is not None and current in path_index:
      # Found a directed cycle
      cycle = path[path_index[current] :]
      chain_len = len(cycle)
      total_value = sum(
        gift_map.get((cycle[i], cycle[(i + 1) % chain_len]), 0)
        for i in range(chain_len)
      )
      chains.append({"chain_length": chain_len, "total_gift_value": total_value})

    visited.update(path)

  if not chains:
    return pd.DataFrame(columns=["chain_id", "chain_length", "total_gift_value"])

  result = pd.DataFrame(chains)
  result = result.drop_duplicates(subset=["chain_length", "total_gift_value"])
  result = result.sort_values(
    ["chain_length", "total_gift_value"], ascending=[False, False]
  ).reset_index(drop=True)
  result["chain_id"] = range(1, len(result) + 1)
  return result[["chain_id", "chain_length", "total_gift_value"]]