How can we detect a simple cycle in a graph ?
Simple Cycle : "Let us denote as a simple cycle a set of v vertices that can be numbered so that the edges will only exist between vertices number 1 and 2, 2 and 3, ..., v - 1 and v, v and 1. "
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
How can we detect a simple cycle in a graph ?
Simple Cycle : "Let us denote as a simple cycle a set of v vertices that can be numbered so that the edges will only exist between vertices number 1 and 2, 2 and 3, ..., v - 1 and v, v and 1. "
Name |
---|
How to "detect" a simple cycle is actually quite easier than how to "find" one.
Consider any connected component of a graph. Let the size of the connected component be N and the number of edges in it be M. The inequality $$$N-1 \le M$$$ must hold, because a graph with N-1 edges is a tree, and removing any edge from a tree causes it to be disconnected.
I claim that any connected component that satisfies $$$M \ge N$$$ has a loop. Proof: Consider the spanning tree of said connected component. This spanning tree only uses up $$$N-1$$$ of the M edges. Since adding any edge to a tree creates a loop, there is at least one loop in this connected component.
Okk . Got it . Thanks a lot .
To implement that, it is usually easiest to use a disjoint set and just check if the two positions were already connected. If there were, you have a cycle.