要求忽略边权小于等于 k 的边时判断有向图中是否存在环。下面的做法( 调用 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;
}