关于强连通分量复习时遇到的事情

ajcxsu
ajcxsu 2018年02月23日
  • 41 次阅读

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

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://acxblog.site/archives/scc_mention.html
本文采用 CC BY-NC-SA 3.0 协议进行许可