PreviousNext
Coding/Graphs and trees

Maximum independent set

Write codeHard35 min

Your task

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.

Examples

max_independent_set(nL: int, nR: int, edges: list[list[int]]) -> int
Example 1
Inputmax_independent_set(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])
Output3