P2661 信息传递Exp.
已更新：update\:on\:2019.9.19
这篇文章说明了tarjan在这道题里的局限性，希望能让更多同学理解普适的最小环求法.
P2661 信息传递
最近刚学完tarjan算法，所以看到这道题的第一想法就是能不能用tarjan来做。试着画了一下，发现可行，
最小环的大小=最小强联通分量的边数=最小强联通分量的点数然后花了三分钟就AC了。
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
int n,ans=0x7f7f7f;
vector<int >g[maxn];
int deep,top,dfn[maxn],low[maxn],color[maxn],stac[maxn],sum;
bool vis[maxn];
void tarjan(int u){
deep+=1;
dfn[u]=deep;
low[u]=deep;
top+=1;
stac[top]=u;
vis[u]=true;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}
else{
if(vis[v]){
low[u]=min(low[v],low[u]);
}
}
}
if(dfn[u]==low[u]){
sum+=1;
vis[u]=false;
color[sum]++;
while(stac[top]!=u){
top--;
vis[stac[top]]=false;
color[sum]++;
}
top--;
}
}
int main(){
scanf("%d",&n);
int x;
for(int i=1;i<=n;i++){
scanf("%d",&x);
g[i].push_back(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=sum;i++)
if(color[i]>1)ans=min(ans,color[i]);//除自环或单个元素
printf("%d\n",ans);
return 0;
}但是！
如此做完之后，我仔细一想，又觉得不是很妙，在纸上比划几下，竟然把这种算法hack掉了！
如图，这是一个强联通分量，但是最小环是3而不是tarjan的6.
不由得惊出了一身冷汗，难道题目如此之水，连这种错误的算法都不能查出来吗？
赶忙回去看题，发现了这样一行：
注意：可能有人可以从若干人那里获取信息， 但是每人只会把信息告诉一个人，即自己的信息传递对象怪不得我的垃圾tarjan能过呢……
那么，既然不是所有的最小环都能够用tarjan算法，并查集怎么样呢？
我们先按上图构造一组数据：
6 7
1 2
2 3
3 4
4 1
2 6
6 5
5 2然后对代码的读入稍作修改，使其可以读入这组数据。
运行tarjan，得到了如下结果：
显然不正确。
我在这里借用前面一位大佬的代码（对不起！）来运行，结果如下:
正确！
为什么呢？我们研究一下，这两份代码有什么不同。
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
int n,m,fa[maxn],ans=0x3f3f3f3f;
int get(int x,int &cnt){//由于cnt要修改，所以得传参
cnt++;
if(fa[x]==x)return x;
else return get(fa[x],cnt);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int cnt=0,f,e;
scanf("%d%d",&f,&e);
if(get(e,cnt)==f){//这里最后也没有连成环
ans=min(ans,cnt);
}else fa[f]=e;//f的父亲节点前进一格，
}
printf("%d\n",ans);
return 0;
}实际上duoluoluo巨佬已经说得很清楚了，
我们在连接一个点到另一个点之前，先用并查集判断是否构成一个环，如果是的话，我们就可以记录下这个答案，然后维护最小的答案。
那么，如果构成一个环的话，怎么记录它的长度呢？
我们可以先定义一个变量cnt，在并查集获取祖先的函数中使cnt的值加1，最后函数结束时就能得到这个环的长度了qwq！
同时，如果构成了一个环，就不需要把这个环的结尾接上，否则会陷入死循环！！由此可见，并查集算法是动态更新的，而tarjan是静态更新的，这就是为什么tarjan在执行时会出错了。
综上所述，虽然在这道题里tarjan算法能够AC，但是它并不能普遍适用。学会并查集的求最小环方法才是硬道理。
最后贴一下测试以上样例的代码
后来发现实际上并查集的做法也不能普遍适用.
注意到这里的所有边权都为1，所以并查集算法才成立.
如果是带权图，并查集和
无向图上据我所知比较方便的是
有向图上求最小环可以使用
枚举每一个点作为起点，在松弛完起点所有的出边后把其
堆优化后时间复杂度为