Цитата:
|
Сообщение от wiki
Граф G называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины.
Если для графа G можно указать пару различных вершин, которые не соединяются простой цепью, то граф называется несвязным.
|
Соответственно, если проблемы с загрузкой, то нужен пример файла.
По кол-ву ребер. Как видно из определений сверху и того, что граф неориентированный, то в данном случае достаточно проанализировать списки и выяснить, какие из них не имеют общих вершин. Точнее надо их сгруппировать так, что бы списки с общими вершинами были в одной группе. кол-во полученных групп будет на 1 больше, чем нужное тебе кол-во ребер. По поводу группировки. После загрузки списков у тебя есть массив этих списков. пытайся их объединить по общим вершинам. Как только ты пройдешь весь массив и не сможешь объединить ни одного списка, то оставщиеся списки - это кол-во несвзанных между собой подграфов. Т.к. граф неориентированный, то достаточно просто соединить любую вершину такого подграфа с любой другой вершиной другого подграфа, что бы связать их, т.е. "организовать" путь между любыми 2мя вершинами в полученном общем графе.
ЗЫ. Не готов так с налета строго доказать, что эта эвристика правильная, но по ощущениям - должно работать. Т.е. полный обход графа тут не нужен. Даже, вроде, в результате задача перестает быть NP-полной. Особенно, если верщины сортировать и использовать двусвязные списки для более быстрого поиска.