POJ 3694 - Network
Problem : Given an undirected graph, and there are q (q<1000) queries. For each query, add an edge between 2 vertices first, then output the number of bridges in current graph.
Solution : Do the tarjan and get the hh value first. For each query, Find two vertices' (u and v) common nearest ancestor w, The decreased bridge is the bridge between u-w and v-w. Then use union-check set to update hh[u] and hh[v] to hh[w].