做的是 草鉴赏 这个题。
模板是按着 受欢迎的牛 来打的。
如下：

void tarjan(int x){
    dfn[x]=low[x]=++idx;
    stk[top++]=x;
    instk[x]=1;
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]){
            tarjan(to[u]);
            low[x]=min(low[x],low[to[u]]);
        }
        else if(instk[to[u]]) low[x]=min(low[x],dfn[to[u]]);
    if(dfn[x]==low[x]) {
        ++cidx;
        do{
            top--;
            scc[stk[top]]=cidx;
        }while(stk[top]!=x);
    }
}

这个代码是 AC 的。

然后我照着打，原本是这样：

void tarjan(int x) {
    dfn[x]=low[x]=++idx;
    stk[top++]=x;
    instk[x]=1;
    for(int u=h1[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            tarjan(to[u]);
            low[x]=min(low[x],low[to[u]]);
        }
        else if(instk[to[u]]) low[x]=min(low[x],dfn[to[u]]);
    if(low[x]==dfn[x]) {
        sidx++;
        do {
            top--;
            scc[stk[top]]=sidx;
        } while(stk[top]!=x) ;
    }
    instk[x]=0; // 区别在这里
}

50 分。
然后又看了一下模板，再改改，把那个 instk 给删了。
7 分。
然后最后改成了：

void tarjan(int x) {
    dfn[x]=low[x]=++idx;
    stk[top++]=x;
    instk[x]=1;
    for(int u=h1[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            tarjan(to[u]);
            low[x]=min(low[x],low[to[u]]);
        }
        else if(instk[to[u]]) low[x]=min(low[x],dfn[to[u]]);
    if(low[x]==dfn[x]) {
        sidx++;
        do {
            top--;
            scc[stk[top]]=sidx;
            instk[stk[top]]=0; // 区别在这里
        } while(stk[top]!=x) ;
    }
}

满分。

洛谷的数据是有多水啊...

本文链接：https://pst.iorinn.moe/archives/scc_mention.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆