传送门:http://acm.hnu.cn/online/?action=problem&type=show&id=12307
题目大意:给定一个联通图,求出能有多少种不同的方式去除两个不同的点使得原图变的不联通。
关于解题:这道是上次校赛的一道题,比赛当时没仔细想,也没仔细看数据,压根就没想枚举割点,后来听解题报告的时候恍然大悟,这道题可以先用tarjan求一次割点,然后对于此次求出的割点,剩下任意的点都可以与割点构成一对(注意判重),对于非割点,那么考虑去除它,再求一次割点,这次出现的那么被去除的点与这次求出的割点同样构成一组(注意去重),那么累加起来就是结果。(PS:我这样写始终WA,于是反向思维,求出去除两个点之后图仍然连通,这样所有的点对,也就是去除非割点后,再求非割点,在用总点对数减去它就AC了)
代码: