Maximum independent set
You are given a bipartite graph with nL left nodes and nR right nodes and edges [a, b]. Return the size of a maximum independent set: the largest set of nodes such that no edge connects two chosen nodes. Constraints: 1 <= nL, nR <= 60.
Implement
max_independent_set(nL: int, nR: int, edges: list[list[int]]) → intExamples
in
[3,3,[[0,0],[0,1],[1,0],[2,2]]]out3What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[3,3,[[0,0],[0,1],[1,0],[2,2]]]3not run yetsample