2020牛客寒假算法基础集训营6 B-图

Ursula ·

更新时间:2024-09-21

· 725 次阅读

2020牛客寒假算法基础集训营6 B-图
思路：
记忆化搜索dfs
分析可知图为出度为1的基环内向树森林，从一个点出发，沿着出边一路走下去，一定会走到一个环。
所以我们选择dfs，当遍历到一个已在dfs栈中的节点时，就说明找到了环，可以结束统计。
但这样是会超时的，于是我们选择带“记忆化”的dfs，从一个点开始沿着出边走下去，每当走到一个在之前某次dfs中经过的点时，就可以利用上一次的答案完成求解。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pairP;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll maxn = 1e6 + 5;
int n,loop;
int to[maxn],f[maxn],cnt[maxn];//f[]记录从当前点走下去一共有多少个环 cnt[]记录step数
bool vis[maxn];
int dfs(int x,int step){
	vis[x]=true;
	cnt[x]=step;
	int tx=to[x];
	if(!vis[tx]){
		int res=dfs(tx,step+1);
		if(loop){
			if(loop==x){//loop用来判断是否出环 自环
				loop=0;
			}
			return f[x]=res;//未出环时环内各点均为res
		}else{
			return f[x]=res+1;//出环后为该点个数+1
		}
	}else{
		if(f[tx]) return f[x]=f[tx]+1;//下一个点搜过了且下一个点有值则为其+1
		else{//下一个点搜过了但是还为0 显然还在遍历环切恰恰是环尾到入环点
			loop=tx;//标记入环点
			if(tx==x) loop=0;//自环
			return f[x]=cnt[x]-cnt[tx]+1;//环的大小为出换点的step-入环点的step+1
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i>to[i];
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=true;
			loop=0;
			dfs(i,1);
		}
	}
	cout<<*max_element(f+1,f+1+n);
	return 0;
}

作者：陆小萌

牛客算法

1024 个赞