A - Don't Detect Cycle Editorial
by 
Astral__
Partial Points
First, if an order of edge additions satisfying the conditions exists, there must be at least one edge that can be added last such that its addition at that point does not violate the conditions.
For such an edge, we can decide to add it last among the yet-to-be-ordered edges. This is justified because adding this edge does not impose restrictions on edges added earlier, nor does it violate the conditions when added.
Once an edge is decided to be added last, it no longer affects the preceding edges, so it can be considered as if it was not present initially. By repeatedly “removing” such edges, we can obtain a solution.
We determine edges that can be added last via a brute-force search. The computational complexity involves removing edges \(M\) times, and within each step, searching for the edge to add last in \(\frac{M}{2}\) iterations on average. Checking for violations during these iterations takes \(O(N + M)\) time (for example, by using lowlink. The condition “a vertex \(v\) is part of a cycle” is equivalent to “there exists an edge directly connected to \(v\) that is not a bridge”). Thus, the total computational complexity is \(O(M^2(M + N))\), allowing us to solve this problem.
Full Points
First, we consider the edges that do not belong to any cycle in the final graph, that is, the bridges.
In fact, the bridges in the final graph can be thought of as being added first from among the edges with an undecided addition order. And also, once decided, it can be treated as if it never existed from the beginning.
explanation
It is acceptable to assume that they are added first among the edges with an undecided addition order
Edges that do not belong to any cycle in the final graph may be constrained by previously added edges, but they do not impose constraints on edges that are added later. Additionally, even if added first, it will not violate any constraints. Therefore, if there exists an addition order that satisfies the conditions, we can assume a new addition order where such edges are added first, and this new order will also satisfy the conditions.
It is acceptable to consider that they never existed from the beginning
Moreover, since the edges added first do not affect the formation of cycles, they do not impose constraints on edges added later.
In graphs where all edges belong to some cycle in the final graph, we ask: can the “edges that can be added last” be identified without brute-force?
Here, we focus on an edge \(e = (u, v)\), where the degrees of both endpoints in the final graph are at most \(2\).
In fact, such an edge \(e\) can also be considered as being added last among the edges with an undecided addition order. And also, once decided, it can be treated as if it never existed from the beginning.
explanation
By deciding to add edge \(e\) last, no constraints will be violated
Let us consider a situation where edge \(e\) cannot be added.
This would be the case if either \(u\) or \(v\) is already included in a cycle in the graph from which edge \(e\) has been removed.
However, since the degrees of both \(u\) and \(v\) in the graph with edge \(e\) removed are at most \(1\), it is impossible for either \(u\) or \(v\) to be included in a cycle.
Therefore, adding edge \(e\) will not violate any constraints.
We will repeat both of these operations as much as possible.
Eventually, if the number of edges planned to be added becomes \(0\), there trivially exists an addition order that satisfies the conditions.
Conversely, consider the case where the number of planned edges does not become \(0\).
In other words, we consider a graph in which every edge is included in a cycle, and the larger of the two endpoint degrees exceeds \(2\).
In fact, it can be said that there is no addition order of edges that satisfies the conditions in such a graph.
proof
Setting terms
Let us arbitrarily take the last edge in a set of edges, denoting it as \(e' = (u', v')\). We will denote the graph with only edge \(e'\) removed as \(g\).
Due to the symmetry of \(u'\) and \(v'\) and the assumptions about the graph, we can assume that the degree of \(v'\) in graph \(g\) is \(\ge 2\).
Here, we can arbitrarily choose \(2\) vertices directly connected to \(v'\) in graph \(g\), denoting them as \(a\) and \(b\).
Proof by contradiction
Assume that \(v'\) is not included in a cycle in \(g\).
Since edge \(e'\) is an edge included in a cycle when added to the graph, there exists a path from \(v'\) to \(a\) that does not use edge \((a, v')\) in the graph obtained by adding edge \(e'\) to \(g\).
However, since \(v'\) is not included in a cycle just before adding edge \(e'\), there would be no such path from \(v'\) to \(a\) prior to the addition of edge \(e'\).
Thus, such a path from \(v'\) to \(a\) in the final graph must pass through edge \(e'\).
In other words, there already exists a simple path from \(u'\) to \(a\) in graph \(g\) that does not include vertex \(v'\).
Similarly, there also exists a simple path from \(u'\) to \(b\) that does not include vertex \(v'\).
By merging these paths, we obtain a path \(a \to u' \to b\) on graph \(g\).
As long as there are edges or vertices appearing more than once in this path, we can delete the portions between them, ultimately obtaining a simple path from \(a\) to \(b\) that does not include vertex \(v'\).
Using this path, we obtain the cycle \(v' \to a \to b \to v'\) on graph \(g\). Thus, the assumption that \(v'\) is not included in a cycle in graph \(g\) leads to a contradiction.
This reasoning translates directly into construction.
Specifically, it can be solved with a computational complexity of \(O(M(N + M))\) by using appropriate algorithms such as low-link to enumerate the bridges of the graph.
posted:
last update: