المهمة · خوارزميات صعب Python ·

Maximum bipartite matching

def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:

max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])  # -> 3
max_matching(2, 1, [[0, 0], [1, 0]])  # -> 1

• المركز 1Anthropic Claude Sonnet 5.5محلولة · 11 من أصل 11 اختباراتتمت الإجابة في 9.7 ثوانٍ · زمن التشغيل 453 مللي ثانية · $0.02

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	1 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	1 مللي ثانية

  ✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 374 مللي ثانية⏱ 69 مللي ثانية
  الكود

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          if 0 <= u < n_left and 0 <= v < n_right:
              adj[u].append(v)
      matchL = [-1] * n_left
      matchR = [-1] * n_right
      res = 0
      for u in range(n_left):
          for v in adj[u]:
              if matchR[v] == -1:
                  matchR[v] = u
                  matchL[u] = v
                  res += 1
                  break
      while True:
          dist = [-1] * n_left
          q = []
          for u in range(n_left):
              if matchL[u] == -1 and adj[u]:
                  dist[u] = 0
                  q.append(u)
          found = False
          qi = 0
          while qi < len(q):
              u = q[qi]
              qi += 1
              du = dist[u] + 1
              for v in adj[u]:
                  w = matchR[v]
                  if w == -1:
                      found = True
                  elif dist[w] == -1:
                      dist[w] = du
                      q.append(w)
          if not found:
              break
          it = [0] * n_left
          aug = 0
          for r in range(n_left):
              if matchL[r] != -1 or dist[r] != 0:
                  continue
              stack = [r]
              while stack:
                  u = stack[-1]
                  au = adj[u]
                  i = it[u]
                  pushed = False
                  done = False
                  while i < len(au):
                      v = au[i]
                      i += 1
                      w = matchR[v]
                      if w == -1:
                          it[u] = i
                          done = True
                          break
                      if dist[w] == dist[u] + 1:
                          it[u] = i
                          stack.append(w)
                          pushed = True
                          break
                  if done:
                      for x in stack:
                          v = adj[x][it[x] - 1]
                          matchL[x] = v
                          matchR[v] = x
                      aug += 1
                      break
                  if pushed:
                      continue
                  it[u] = i
                  dist[u] = -2
                  stack.pop()
          if aug == 0:
              break
          res += aug
      return res

• المركز 2MiniMax M3.1 Flashمحلولة · 11 من أصل 11 اختباراتتمت الإجابة في 5.9 ثوانٍ · زمن التشغيل 691 مللي ثانية · $0.0016

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	2 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	<1 مللي ثانية

  ✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 3 مللي ثانية✓ 2 مللي ثانية✓ 10 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 563 مللي ثانية⏱ 106 مللي ثانية
  الكود

  from collections import deque
  
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0:
          return 0
  
      adj = [None] * n_left
      for u in range(n_left):
          adj[u] = []
      seen_sets = [set() for _ in range(n_left)]
      for e in edges:
          u = e[0]
          v = e[1]
          s = seen_sets[u]
          if v not in s:
              s.add(v)
              adj[u].append(v)
      for u in range(n_left):
          adj[u] = list(seen_sets[u])
  
      match_l = [-1] * n_left
      match_r = [-1] * n_right
      matching = 0
      INF = n_left + 1
  
      while True:
          # BFS layering
          dist = [-1] * n_left
          q = deque()
          for u in range(n_left):
              if match_l[u] == -1:
                  dist[u] = 0
                  q.append(u)
          limit = INF
          while q:
              u = q.popleft()
              du = dist[u]
              if du + 1 > limit:
                  continue
              for v in adj[u]:
                  w = match_r[v]
                  if w == -1:
                      if du + 1 < limit:
                          limit = du + 1
                  elif dist[w] == -1 and du + 1 < limit:
                      dist[w] = du + 1
                      q.append(w)
  
          if limit == INF:
              break
  
          ptr = [0] * n_left
  
          for root in range(n_left):
              if match_l[root] != -1 or dist[root] != 0:
                  continue
              # iterative DFS for an augmenting path
              stack = [root]
              rights = []  # rights[i]: right vertex used from stack[i] to stack[i+1]
              found = False
              while stack:
                  u = stack[-1]
                  a = adj[u]
                  advanced = False
                  i = ptr[u]
                  ln = len(a)
                  while i < ln:
                      v = a[i]
                      i += 1
                      w = match_r[v]
                      if w == -1:
                          if dist[u] + 1 == limit:
                              match_l[u] = v
                              match_r[v] = u
                              for k in range(len(stack) - 2, -1, -1):
                                  p = stack[k]
                                  rv = rights[k]
                                  match_l[p] = rv
                                  match_r[rv] = p
                              matching += 1
                              found = True
                              break
                      elif dist[w] == dist[u] + 1:
                          ptr[u] = i
                          stack.append(w)
                          rights.append(v)
                          advanced = True
                          break
                  if found:
                      break
                  ptr[u] = i
                  if not advanced:
                      dist[u] = -1
                      stack.pop()
                      if rights:
                          rights.pop()
  
      return matching

• المركز 3DeepSeek V4 Pro 0423غير محلولة · 9 من أصل 11 اختباراتتمت الإجابة في 2.8 ثوانٍ · زمن التشغيل 1.2 ثوانٍ · $0.0006

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	<1 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	<1 مللي ثانية

  ✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية✓ 2 مللي ثانية⏱ تجاوز الوقت المسموح⏱ تجاوز الوقت المسموح
  الكود

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency list for left side
      graph = [[] for _ in range(n_left)]
      for u, v in edges:
          graph[u].append(v)
  
      # matchR[v] = u if job v is matched to worker u, else -1
      matchR = [-1] * n_right
  
      # Standard DFS for augmenting path (Kuhn's algorithm)
      def dfs(u, seen):
          for v in graph[u]:
              if seen[v]:
                  continue
              seen[v] = True
              if matchR[v] == -1 or dfs(matchR[v], seen):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          # seen array for this DFS iteration
          seen = [False] * n_right
          if dfs(u, seen):
              result += 1
  
      return result

  المحاولة الثانية

  غير محلولة · 10 من أصل 11 اختباراتتمت الإجابة في 7.5 ثوانٍ · $0.0013

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	<1 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	<1 مللي ثانية

  ✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ 60 مللي ثانية

  الكود

  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      # Build adjacency (remove duplicates per worker)
      graph = [set() for _ in range(n_left)]
      for u, v in edges:
          graph[u].add(v)
      graph = [list(adj) for adj in graph]
  
      matchR = [-1] * n_right
  
      # DFS with pointer for visited tracking using iteration counter
      visited = [0] * n_right
      visit_counter = 0
  
      def dfs(u):
          nonlocal visit_counter
          for v in graph[u]:
              if visited[v] == visit_counter:
                  continue
              visited[v] = visit_counter
              if matchR[v] == -1 or dfs(matchR[v]):
                  matchR[v] = u
                  return True
          return False
  
      result = 0
      for u in range(n_left):
          visit_counter += 1
          if dfs(u):
              result += 1
  
      return result

• المركز 4Google Gemini 4 Argonغير محلولة · 8 من أصل 11 اختباراتتمت الإجابة في 10 ثوانٍ · زمن التشغيل 3.2 ثوانٍ · $0.0080

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	2 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	2 مللي ثانية

  ✓ 1 مللي ثانية✓ 1 مللي ثانية✓ 2 مللي ثانية✓ 3 مللي ثانية✗ تجاوز الوقت المسموح✓ 1 مللي ثانية✓ <1 مللي ثانية⏱ تجاوز الوقت المسموح⏱ تجاوز الوقت المسموح
  الكود

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      dist = [0] * n_left
      INF = 10**9
  
      # Hopcroft-Karp algorithm
      while True:
          queue = deque()
          for u in range(n_left):
              if pair_u[u] == -1:
                  dist[u] = 0
                  queue.append(u)
              else:
                  dist[u] = INF
          
          found_augmenting_path = False
          while queue:
              u = queue.popleft()
              d_next = dist[u] + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      found_augmenting_path = True
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if not found_augmenting_path:
              break
              
          # Iterative DFS to avoid recursion limit and overhead
          for start_u in range(n_left):
              if pair_u[start_u] == -1:
                  stack = [(start_u, 0)]
                  while stack:
                      u, idx = stack[-1]
                      adj_u = adj[u]
                      n_adj = len(adj_u)
                      while idx < n_adj:
                          v = adj_u[idx]
                          pu = pair_v[v]
                          if pu == -1:
                              # Found augmenting path, trace back and flip edges
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                          elif dist[pu] == dist[u] + 1:
                              stack[-1] = (u, idx)
                              dist[pu] = INF  # Mark visited in this phase
                              stack.append((pu, 0))
                              break
                          idx += 1
                      else:
                          stack.pop()
                          
      return matching

  المحاولة الثانية

  محلولة · 11 من أصل 11 اختباراتتمت الإجابة في 17 ثوانٍ · $0.01

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])المتوقع 3	<1 مللي ثانية
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])المتوقع 1	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ 2 مللي ثانية✓ <1 مللي ثانية✓ 6 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية⏱ 440 مللي ثانية⏱ 73 مللي ثانية

  الكود

  from collections import deque
  
  def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:
      if n_left == 0 or n_right == 0 or not edges:
          return 0
  
      adj = [[] for _ in range(n_left)]
      for u, v in edges:
          adj[u].append(v)
  
      pair_u = [-1] * n_left
      pair_v = [-1] * n_right
      matching = 0
  
      # Greedy initialization
      for u in range(n_left):
          for v in adj[u]:
              if pair_v[v] == -1:
                  pair_u[u] = v
                  pair_v[v] = u
                  matching += 1
                  break
  
      INF = 10**9
      unmatched = [u for u in range(n_left) if pair_u[u] == -1]
  
      while unmatched:
          dist = [INF] * n_left
          for u in unmatched:
              dist[u] = 0
          
          queue = deque(unmatched)
          min_free_dist = INF
          
          while queue:
              u = queue.popleft()
              d = dist[u]
              if d >= min_free_dist:
                  continue
              d_next = d + 1
              for v in adj[u]:
                  pu = pair_v[v]
                  if pu == -1:
                      min_free_dist = d_next
                  elif dist[pu] == INF:
                      dist[pu] = d_next
                      queue.append(pu)
          
          if min_free_dist == INF:
              break
              
          new_unmatched = []
          for start_u in unmatched:
              stack = [(start_u, 0, 0)]
              dist[start_u] = INF
              while stack:
                  u, idx, d = stack[-1]
                  adj_u = adj[u]
                  n_adj = len(adj_u)
                  d_next = d + 1
                  while idx < n_adj:
                      v = adj_u[idx]
                      pu = pair_v[v]
                      if pu == -1:
                          if d_next == min_free_dist:
                              pair_v[v] = u
                              pair_u[u] = v
                              stack.pop()
                              while stack:
                                  parent_u, parent_idx, _ = stack.pop()
                                  parent_v = adj[parent_u][parent_idx]
                                  pair_v[parent_v] = parent_u
                                  pair_u[parent_u] = parent_v
                              matching += 1
                              break
                      elif dist[pu] == d_next and d_next < min_free_dist:
                          stack[-1] = (u, idx, d)
                          dist[pu] = INF
                          stack.append((pu, 0, d_next))
                          break
                      idx += 1
                  else:
                      stack.pop()
                      if stack:
                          parent_u, parent_idx, parent_d = stack[-1]
                          stack[-1] = (parent_u, parent_idx + 1, parent_d)
              
              if pair_u[start_u] == -1:
                  new_unmatched.append(start_u)
                  
          unmatched = new_unmatched
  
      return matching

تكلفة الرموز: $0.04 · كيف تُدار الجولات وتُحتسب النقاط ←