WA #1 #2 #12 85pts警示后人

ssilrrr @ 2022-10-12 07:48:41

by ssilrrr @ 2022-10-12 07:51:33

void tarjan(int u,int fa){
    bool f=0;//特判
    dfn[u]=low[u]=++tot;
    //if(u==fa&&v[u].empty()){anss.pb({u});return;}
    stk.push(u);
    for(auto i:v[u]){
        if(!dfn[i]){tarjan(i,u);low[u]=min(low[u],low[i]);
        if(low[i]>dfn[u]){int l;vector<int> vi;do{l=stk.top();vi.pb(l);stk.pop();}while(l!=i);anss.pb(vi);}}
        else if(i!=fa||f) low[u]=min(low[u],dfn[i]);//
        if(i==fa)f=1;//
    }if(u==fa){int l;vector<int> vi;do{l=stk.top();vi.pb(l);stk.pop();}while(l!=u);anss.pb(vi);}
}

by dbxxx @ 2022-10-12 13:52:07

@ssilrrr 麻烦了，dfs 第二个参数传上次来访的边即可。

inline void tarjan(int u, int ls) {
    dfn[u] = low[u] = ++times;
    s.push(u);

    for (pii e : G[u]) {
        int v = e.first, id = e.second;
        if (!dfn[v]) {
            tarjan(v, id);
            gmi(low[u], low[v]);
        } else if (id != ls) {
            gmi(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        ++ent;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            ecc[ent].push_back(x);
            if (x == u)
                break;
        }
    }
}

by dbxxx @ 2022-10-12 13:53:05

gmi 函数

inline bool gmi(int &a, int b) {
    return b < a ? a = b, true : false;
}

by ssilrrr @ 2022-10-12 22:32:32

@dbxxx 理解您的意思，不过咱俩存图方式不一样，我是直接用vector<int>，而不是用pii带上入边序号，在如下代码上可能有体现：

fe(i,n){if(!dfn[i]){tarjan(i,i);}}

按您的方法大概是

tarjan(i,0);//-1

那么对于前者来说，应该没有别的判重边选择了。。

by dbxxx @ 2022-10-13 00:06:55

@ssilrrr 但是这个确实绑个 pii 能少不少麻烦而且更为直观体现了“重边”其实就是在，原来不能回到祖先 fa 的基础上，变为不能通过来的那条边回去，但可以通过别的边（重边）回到 fa。

事实上我压根没看懂您那个代码怎么判断的（