A faster way to find out whether a cycle is formed if any node has at most 2 edges?

First of all, no homework.

Here is the problem:

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.

Input:

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.

My approach (too slow):

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 for开发者_StackOverflowmed!
3.3.2) If not, merge two links.

Please recommend a faster algorithm, and the data structures for the algorithm. Thank you.

The standard algorithm for an undirected graph is to simply run a depth first search on it, keeping track of the nodes on the current path. If you run into a visited node, then you have a cycle.

Since each node has at most 2 incident edges, remove any nodes with 0 edges and then repeatedly remove any node that has only a single incident edge (and the corresponding edge). If you have a cycle you will reach a stage where there are no nodes that you can remove, but there will still be nodes left. If there is no cycle then you will terminate having removed all the nodes.

Edit: To deal with possibly invalid input and to be more explicit about the underlying data-structure.

As the data is read in build up a data-structure that is indexed by node ID and, for each indexed entry, contains a list of the nodes incident to that node. [I.e. as each edge is read in there are two entries to be made, one for each of the nodes.] As the data comes in remove duplicates and spot if any node is incident to too many edges. This is linear.

Keep a list of nodes with a single incident edge. At each step in the algorithm you pick any node from this list and, having removed the edge put the node to which it is linked in this list (if necessary). [If a node was already in the list you can either remove it or modify the previous step to just ignore any edges, taken from the list, that have no more incident edges.]

An edge is added at most once to the list and each iteration removes an edge from that list. Hence linear.

You can pick Prim's or Kruskal's algorithms for creating shortest spanning trees. Basically they both attempt to add edges of least weight to a new tree while not creating a circuit. You just have to modify the algorithm a tad so that in the event of a circuit creation, then you just break the procedure.

They both run as O(e log e) if I remember right (e: edges), but it'll likely be much faster as you can break of very early.