听灌多
  • 板块灌水区
  • 楼主_reut_lg2023
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/23 15:12
  • 上次更新2024/5/23 18:59:06
查看原帖
听灌多
1066045
_reut_lg2023楼主2024/5/23 15:12

要求忽略边权小于等于 kk 的边时判断有向图中是否存在环。下面的做法( 调用 circle(k) )有什么问题吗?

void dfs(int x,int k)
{
	dfn[x]=low[x]=++dfni,stc[++top]=x,instc[x]=1;
	int siz=ed[x].size();
	for(int i=0;i<siz;i++)
	{
		int v=ed[x][i];
		if(w[mp(x,v)]<=k)
			continue;
		if(!dfn[v])
			dfs(v,k),low[x]=min(low[x],low[v]);
		else if(instc[v])
			low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x])
	{
		scc++;
		while(stc[top]!=x)
			pop(stc[top]);
		pop(x);
	}
}
int circle(int k)
{
	memset(dfn,0,sizeof(dfn)); 
	dfni=0,scc=0,top=0;
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			dfs(i,k);
	if(scc!=n) return 1;
	return 0;
}
2024/5/23 15:12
加载中...