General Graph Matching Problem

General Graph Matching Problem — ExecCode Hard DSA Practice

Solve the General Graph Matching problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Students form a club graph that is not necessarily bipartite. You want the maximum number of disjoint buddy pairs (a matching in a general graph). Odd cycles need Edmonds' blossom shrinking. The answer is the number of matched edges. Undirected edges [u, v]. Return the maximum matching size (edge count, not vertex count). You are given: n — vertices edges — undirected pairs Return maximum number of disjoint edges. A triangle matches at most 1 edge.

Examples

Input {'n': 3, 'edges': [[0, 1], [1, 2], [2, 0]]}; Output 1. Input {'n': 4, 'edges': [[0, 1], [2, 3]]}; Output 2. Input {'n': 2, 'edges': []}; Output 0

Constraints

Self-loops ignored n is small in tests, blossom is the intended method

Practice General Graph Matching free on ExecCode. Browse DSA problems, topic map, and placement guides.