题    目    传    送    们    在    这

题目大意

有一个由n个点和m条边组成的无向联通图。

现在有Q个操作，每次操作可以在点x，y之间连一条边。

问你每次操作后有多少个多少个桥（即删掉后就会使图不联通的边）。

解题思路

根据边双联通的定义，我们知道将边双联通分量缩点后的图，其中的边即为桥。

我们将这个图缩点，就变成了一棵树。

而每次在两个不同的边双联通分量x，y之间加边后，就出现了一个包含x，y的环，其中原先这颗树上x，y的树上最短路径就不在是边。

所以对于每个x，y，我们求出它的最近公共祖先z，其中包含的桥的数量为x的高度+y

poj3694 network（边双联通分量+lca+并查集）