1739. Does Any Link Sit On Two Loops

An UNDIRECTED graph has n vertices and m edges. It is a CACTUS when no edge lies on two different cycles, where a cycle is a closed walk using no edge twice. Print Yes if the graph is a cactus and No otherwise.

1-2, 2-3, 3-1 -> Yes one cycle, each edge on it once 1-2, 2-3, 3-1, 3-4, 4-5, 5-3 -> Yes two cycles sharing only a vertex 1-2, 2-3, 3-4, 4-1, 1-3 -> No the edge 1-3 splits the square into two cycles and 1-2 is on two of the three 1-2, 1-2 -> Yes one cycle of length two 1-2, 1-2, 1-2 -> No three copies give three cycles, and each edge is on two of them 1 vertex, no edges -> Yes nothing to violate

Trees are cacti, since they have no cycles at all. A cactus is exactly a graph whose cycles are edge-disjoint, which makes many hard problems easy on it, and "is this input a cactus" is a real check inside those algorithms.

## The three things that have to be said

directed? no. self-loops? allowed, and a self-loop IS a cycle, of one edge. It is on no other cycle, so self-loops never spoil a cactus, and two self-loops on the same vertex are two edge-disjoint cycles and still fine. parallel edges? allowed. Two copies of an edge form one cycle, which is fine; three copies form three cycles sharing edges, which is not. disconnected? allowed, and every piece must be a cactus.

## What most people try first

Counting: a connected cactus satisfies m <= n + (number of cycles) - 1, or some variant. Counting arguments do not settle it. 1-2, 2-3, 3-4, 4-1, 1-3 has n = 4 and m = 5, and so does 1-2, 2-3, 3-1, 1-4, 4-2 on four vertices; both have the same counts and the first is not a cactus while a graph of two triangles joined at a vertex with n = 5, m = 6 is. Edge and vertex counts cannot see WHICH edges the cycles share.

The honest brute force enumerates cycles and counts how many contain each edge. That is what this problem's oracle does, and it is exponential.

## Each non-tree edge covers a stretch of the tree

Run problem 1728's search. Every non-tree edge joins a vertex to one of its own ancestors, since an undirected search has no cross edges. Such an edge, together with the tree path between its two ends, forms a cycle, and these are exactly the independent cycles of the graph.

the graph is a cactus <=> no TREE EDGE is covered by two non-tree edges

Forwards: if a tree edge is covered by two non-tree edges, those two cycles share it, so it is on two cycles. Backwards: if every tree edge is covered at most once, then any two of the basic cycles are edge-disjoint, and every cycle of the graph is a combination of basic ones, so no edge is reused.

## Counting the coverings without walking any path

Walking the tree path for each non-tree edge would be O(n m). Instead use a DIFFERENCE along the tree. For a non-tree edge whose deeper end is a and shallower end is b:

cnt[a] += 1 cnt[b] -= 1

Then sweep the search's entry order BACKWARDS, adding each cnt[v] into cnt[par[v]]. After that sweep, cnt[v] is exactly the number of non-tree edges covering the tree edge from par[v] down to v, because a vertex on the covered stretch collects the +1 from below and only vertices at or above b also collect the cancelling -1.

Answer Yes exactly when every cnt[v] with v having a parent is at most 1.

## Which endpoint is deeper

The one with the LARGER entry time. That is the only place the entry times are needed for anything other than the covering count, and getting it the wrong way round makes the differences cancel in the wrong direction and reports almost everything as a cactus.

## Cost

Time O(n + m log m), space O(n + m): one search, one pass over the edges, one backwards sweep. The search is ITERATIVE, since a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

## Related

Problem 1736 counts the blocks, and a cactus is exactly a graph every one of whose blocks is a single edge or a single cycle. Problem 1729 is the special case of asking which tree edges are covered ZERO times.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur, and a self-loop is a cycle of one edge - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected