В задаче надо найти максимальное независимое множество. Но есть несколько вопросов.

1) Объясните почему граф двудольный?

2) Объясните теорему Кёнинга, максимальное паросочетание = максимальное независимое множество в двудольном графе?

Ссылка на задачу

Заранее спасибо.

Завершилась Седьмая командная олимпиада. Ссылка на задачи. Как решать B, D и F. Заранее спасибо.