紧张板凳

文章
8
资源
0
加入时间
3年0月9天

CodeForces 292D Connected Components (并查集+YY)

很有意思的一道并查集 题意:给你n个点(<=500个),m条边(<=10000),q(<=20000)个询问。对每个询问的两个值xi yi,表示在从m条边内删除从xi到yi的边后连接剩下的边,最后求连通块的总个数求连通块的个数很容易想到并查集,即把每两块并在一起(祖先任选),可以相连就减一。但是每次询问最多需要m次维护。而某两个点可能直接或间接相连多遍,所以删边后此边上的两个点就不一定不相连(离线