一种多一个log但是码量吊打tarjan的算法
  • 板块学术版
  • 楼主Eric998
  • 当前回复20
  • 已保存回复20
  • 发布时间2022/8/1 18:26
  • 上次更新2023/10/27 17:28:44
查看原帖
一种多一个log但是码量吊打tarjan的算法
678534
Eric998楼主2022/8/1 18:26

求一个有向图的最大环,保证此有向图每个点至多一条出边(可以没有)

算法:维护以下内容

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清空;
输出答案(此时答案是最大的环);
2022/8/1 18:26
加载中...