Luogu P2661 – 并查集

  • 2018-11-27
  • 163
  • 0
  • 0

PROBLEM

https://www.luogu.org/problemnew/show/P2661

ANALYSIS

找到有向图中最小的环。n个点,n条边,n<2*10^5

SOLUTION

首先是两种弱智模拟做法,STL真的降智。

TLE, 80

TLE, 80
比较常规的正确做法:使用并查集,这里算并查集的时候要算一下距离祖先的距离。或许这就是这道题唯一要注意一下的点了吧。

AC

 

REFERENCE

  1. https://www.luogu.org/problemnew/show/P2661

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

评论

还没有任何评论,你来说两句吧