Множество с максимальной мощностью.

[Guliashik]

Дана таблица $N \times M$, содержащая пустые и непустые клетки. Известны координаты непустых клеток. Найти множество непустых клеток максимальной мощности, такое что, любые два элемента этого множества (с индексами $i,j$) удовлетворяют всем условиям: $x_i \neq x_j , y_i \neq y_j , i \neq j$, где $x, y$ - координаты.
Есть ли какой-нибудь алгоритм сложности $O(NM)$ для решения этой задачи?

[venco]

Классическая задача Bipartite matching - вариант Max flow.
В вашем случае быстрее, пожалуй, Hopcroft–Karp algorithm.

[whitefox]

Погуглите "Максимальное паросочетание".