Идея следующая - загнать футбольные команды в граф, где вершины - команды, а рёбра - показатель того, что в командах есть дублирующиеся игроки, после чего задача сводится к задаче о независимом множестве (http://ru.wikipedia.org/wiki/Задача_о_независимом_множестве).
Картинка:
Там кажется, что 2 и 5 связаны - это не так. 2 и 5 по отдельности связаны с 15-ю.
В коде неоптимально вычисляется пересечение - достаточно самого факта, а вычисляем пересечение целиком. Можно заоптимизировать.
Надо сказать, что поскольку задача о независимом множестве NP-полная, а "Легенды футбола" сводится к ней за полиномиальное время, то и "Легенды футбола" NP-полная задача, и нечего комплексовать, что не можем придумать к ней оптимального алгоритма. Тут и подходят-то только поиск с возвратом, жадный поиск, A* и их друзья.
[1] "Решение:"
[1] "Аякс Амстердам 1994-95"
[1] "Ювентус 1995-96"
[1] "Манчестер Юнайтед 1998-99"
[1] "Динамо Киев 1990-2000"
[1] "Реал Мадрид 2001-02"
[1] "Арсенал 2003-04"
[1] "Ливерпуль 2005-06"
[1] "Барселона 2005-06"
[1] "Милан 2007-08"