2019.8.27刷题统计

今天是连续打卡的第51天。

第一题:1161

这道题昨天一直没做出来。上网搜了题解,代码与其不同,但总体思路相同。结果题解代码过了,我的代码却没过。

晚上研究数据,发现这道题所有数据的割点数都很少,可以用暴力算法过。

思路:

①用tarjan算法求割点模板,求出哪个点是割点

②枚举每个割点,在不经过其的情况下求联通块个数。

理论上复杂度应该在105以内。

最后交上发现,由于这道题的数据较为特殊,暴力比正解快!

AC代码:

 第二题:1162

又是一道由于没开long long而耽误时间的题。

其实这道题(如果开了long long)根据下面提示中的公式做很简单。

AC代码:

今天完成Tarjan求割点、割边的所有题目,明天开始Tarjan求强联通分量。

原文地址:https://www.cnblogs.com/wangximing/p/11420715.html