我们称无向图g={ve}g=\{ve\}g={ve}中的一条

我们称无向图G={VE}G=\{VE\}G={VE}中的一条边eee为桥，当且仅当删除这条边后，图中的连通分量数量增加。桥也称为割边。

我们称无向图G={VE}G=\{VE\}G={VE}中的一个顶点vvv为割点，当且仅当删除这个顶点（及所有与其相连的边）后，图中的连通分量数量增加。

利用Tarjan算法，可以经过一次DFS，在O(V+E)O(V+E)O(V+E)的时间内求出图中的所有桥和割点。

Tarjan算法的核心思想是，除了记录节点的DFS序dfn[u]dfn[u]dfn[u]，同时用数组low[u]low[u]low[u]记录从uuu出发，在不经过从其父节点到其的那条边的情况下，所能到达的节点中最小的DFS序。

本题官方题解提供的是并查集解法，但也可以通过Tarjan算法，从最后一条边开始依次判断是否桥边。如果不是桥边，则是一个冗余连接，可以将其删除。