求一个有向图的最大环,保证此有向图每个点至多一条出边(可以没有)
算法:维护以下内容
dfn:时间戳数组
set lft:未遍历的点
set ddf:此轮遍历的点
mx:答案
num:此时的时间戳
dfs(u)过程:
1.从lft取出u;
2.将u放入ddf;
3.将u打上时间戳(dfn[u]=num);
4.num加1;
5.如果u有出边{
如果出边指向的点已经被打上时间戳{
如果出边指向的点在ddf内 mx=max(mx,num-出边指向的点的时间戳);
停止递归;
}
dfs(出边指向的点);
}
流程:
重复执行直到lft为空:
dfs(lft的第一个数);
ddf清空;
输出答案(此时答案是最大的环);