Number of Single-Cycle Components

Number of Single-Cycle Components is a clean graph-counting problem that hides a tiny, beautiful observation: you do not need to trace any cycle at all. A connected component is a single cycle exactly when every vertex in it has degree 2 — and degrees are trivial to count.

The slow way first

The literal approach is to actually walk each component and try to confirm it is one big loop: start somewhere, follow edges, and check that you come back to the start having used every vertex and edge exactly once. That works, but the bookkeeping (which edge did I already use, did I branch) is fiddly and error-prone.

The question to ask: what makes a loop a loop? In a single cycle, every vertex sits between exactly two neighbors — the one before it and the one after it. No more, no fewer.

The idea: a cycle means every degree is 2

The degree of a vertex is the number of edges touching it. Two facts pin down a single cycle:

• In a cycle, every vertex has degree exactly 2.
• If even one vertex has degree 1 (a dangling endpoint) or degree 3+ (a branch), the component is not a clean loop.

So the whole algorithm is: count every vertex's degree, find each connected component with a DFS, and check whether all vertices in that component have degree 2. Count the components that pass.

The connectivity (DFS reaching every vertex in the component) plus every-degree-2 together guarantee a single closed loop — you cannot have two separate loops in one connected component if every degree is exactly 2.

Walk through it

Step through the animation. First we tag every vertex with its degree. The triangle A-B-C lights up as one component — all three have degree 2, so it is a single cycle and the counter ticks to 1. Then the path D-E-F lights up — but D and F have degree 1, so it fails the test and is skipped. The final answer is 1.

Pseudocode

count the degree of every vertex (one pass over the edge list)
seen = empty set
answer = 0
for each vertex v:
    if v not in seen:
        comp = []                      # collect this component with DFS
        dfs(v) -> add every reached vertex to seen and to comp
        if every vertex x in comp has degree[x] == 2:
            answer += 1                # this component is a single cycle
return answer

The Python solution

def count_single_cycles(n, edges):
    adj = build_adjacency(n, edges)
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1; deg[v] += 1
    seen = set()
    def dfs(v, comp):
        seen.add(v); comp.append(v)
        for w in adj[v]:
            if w not in seen: dfs(w, comp)
    count = 0
    for v in range(n):
        if v not in seen:
            comp = []; dfs(v, comp)
            if all(deg[x] == 2 for x in comp): count += 1
    return count

• adj is the adjacency list; deg is one pass over the edges to count how many edges touch each vertex.
• seen marks vertices already assigned to a component, so each component is processed once.
• dfs(v, comp) collects every vertex reachable from v into comp — that is one connected component.
• The outer loop starts a fresh DFS from any unseen vertex, so it discovers every component.
• Line 15 is the heart: all(deg[x] == 2 for x in comp) — the component counts only if every one of its vertices has degree 2.

Complexity

We touch each vertex and edge a constant number of times, so the whole thing is linear in the size of the graph.

When this pattern shows up

Practice