algorithm - 如果任何节点最多有 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

无向图的标准算法是简单地运行一个 depth first search在其上，跟踪当前路径上的节点。如果你遇到一个访问过的节点，那么你就有了一个循环。