P6658 Three-Edge-Connected Components

For an undirected graph $G = (V, E)$. - We say two vertices $u, v ~ (u, v \in V, u \neq v)$ are three-edge-connected if and only if there exist three paths from $u$ to $v$ that do not share any common edges. - We say a vertex set $U ~ (U \subseteq V)$ is a three-edge-connected component if and only if for any two vertices $u', v' ~ (u', v' \in U, u' \neq v')$, they are three-edge-connected. - We say a three-edge-connected component $S$ is a maximal three-edge-connected component if and only if there does not exist a vertex $u \not \in S$ with $u \in V$ such that $S \cup \{u\}$ is also a three-edge-connected component.

Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, where $V = \{1, 2, \ldots, n\}$, find all of its maximal three-edge-connected components.

The first line contains two integers $n, m$, representing the number of vertices and the number of edges. The next $m$ lines each contain two integers $u, v$, representing an edge in the graph.

The first line outputs an integer $s$, representing the number of maximal three-edge-connected components. Then output $s$ lines. Each line contains several integers, representing all vertices in one maximal three-edge-connected component. For each maximal three-edge-connected component, output its vertices in increasing order of their labels. For all maximal three-edge-connected components, output them in increasing order of the smallest vertex label in each set.

#### Explanation for Sample 1  As shown in the figure, there are three paths from $1$ to $3$: $(1, 2, 3)$, $(1, 3)$, and $(1, 4, 3)$. They do not share any edges with each other. Therefore, $1$ and $3$ are in the same three-edge-connected component. Since vertices $2$ and $4$ both have degree only $2$, it is impossible for them to have three edge-disjoint paths to other vertices, so each of them forms a three-edge-connected component by itself. --- #### Constraints - For $30\%$ of the testdata, $n \le 100$, $m \le 200$. - For $50\%$ of the testdata, $n \le 1000$, $m \le 2000$. - For $80\%$ of the testdata, $n \le 10 ^ 5$, $m \le 2 \times 10 ^ 5$. - For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10 ^ 5$, $1 \le u, v \le n$. Multiple edges and self-loops may exist. --- #### Source This problem is adapted from [Three-Edge-Connected Components](https://judge.yosupo.jp/problem/three_edge_connected_components)。 Translated by ChatGPT 5