Components of edge biconnectivity#2274
In graph theory, a component of edge biconnectivity in a graph (V, E) is defined as the largest subset of vertices S \subset V such that for any two distinct vertices \{u, v\} \subset S, there exist at least two edge-disjoint paths between and .
Given an undirected graph, you need to identify its edge biconnected components.
The first line of the input contains two integers and — the number of vertices and edges in the graph, respectively (n \leq 20000, m \leq 200000). The next lines each describe an edge with two integers b_j and e_j. These indicate the vertices connected by the edge (1 \leq b_j, e_j \leq n).
On the first line, print the integer — the number of edge biconnected components in the graph. On the second line, print integers a_1, a_2, \ldots, a_n, not exceeding , where a_i indicates the edge biconnected component to which the -th vertex belongs.
Example 1