Более быстрый способ узнать, образован ли цикл, если какой-либо узел имеет не более 2 ребер?

Question

Прежде всего, без домашней работы.

---

Вот проблема:

An undirected unweighted graph has N nodes.
Any node can have at most 2 edges to different nodes.
I need to know whether at least a cycle is formed.

Ввод:

M pairs of integers, as edges.
There can be duplicates, like "2 3" and "3 2".
The data may be invalid, for example: "1 2" "1 3" "1 4". The program needs to detect this.

---

Мой подход (слишком медленно):

0.1) A set for edges to detect duplicates. (C++ e.g.: std::set<int>)
0.2) A map for nodes to count how many edges from each node. (std::map<int,int>)
0.3) A list for links. A link is a set of connected nodes. (std::list<std::set<int> >)

1) Read in an edge, and change the edge to ascending order, e.g.: "3 2" -> "2 3".

2.1) If the edge has already be "drawn", skip and go to 1);
2.2) If either vertex has already got 2 edges, invalid! 
2.3) Otherwise, check whether either of the nodes has already been in a link.

3.1) If neither, create a new link and add to the list.
3.2) If only one, add the single one to the link.
3.3) If both,
3.3.1) If in the same link, a cycle has been formed!
3.3.2) If not, merge two links.

---

Пожалуйста, порекомендуйте более быстрый алгоритм и структуры данных для этого алгоритма.Спасибо.

Answer 1

Стандартный алгоритм для неориентированного графа состоит в том, чтобы просто выполнить поиск в глубину вначале, отслеживая узлы на текущем пути. Если вы столкнетесь с посещенным узлом, то у вас будет цикл.

Answer 2

Поскольку каждый узел имеет не более 2 падающих ребер, удалите все узлы с 0 ребрами, а затем повторно удалите все узлы, у которых есть только одно падающее ребро (и соответствующее ребро).Если у вас есть цикл, вы достигнете стадии, когда нет узлов, которые вы можете удалить, но все равно останутся узлы.Если цикла нет, вы прекратите удаление всех узлов.

Редактировать: Чтобы иметь дело с, возможно, неверным вводом и быть более точным в отношении базовой структуры данных.

Поскольку данные считываются, создается структура данных, которая индексируется по идентификатору узла и для каждой индексированной записи содержит список узлов, инцидентных этому узлу.[Т.е., когда каждое ребро считывается, нужно сделать две записи, по одной для каждого из узлов.] Поскольку данные поступают, удалите дубликаты и определите, нет ли какого-либо узла в слишком большом количестве ребер.Это линейно.

Храните список узлов с одним краем инцидента.На каждом шаге алгоритма вы выбираете любой узел из этого списка и, удалив ребро, помещаете узел, с которым он связан, в этот список (при необходимости).[Если узел уже был в списке, вы можете либо удалить его, либо изменить предыдущий шаг, чтобы просто игнорировать любые ребра, взятые из списка, у которых больше нет инцидентных ребер.]

Ребро добавляется не болееодин раз в список, и каждая итерация удаляет ребро из этого списка.Следовательно, линейный.

Answer 3

Вы можете выбрать алгоритмы Прима или Крускала для создания кратчайших связующих деревьев.По сути, они оба пытаются добавить ребра с наименьшим весом к новому дереву, не создавая цепи.Вам просто нужно немного изменить алгоритм, чтобы в случае создания схемы вы просто нарушали процедуру.

Они оба работают как O (e log e), если я правильно помню (e: edge), но, скорее всего, это будет намного быстрее, так как вы можете сломаться очень рано.