模板

基环树也可以直接套强连通缩点给秒了,但是事实上假如不需要缩点的话有更简单的写法。

主要维护两种操作:
op1:处理这个节点不在环时怎么处理。
op2:处理这个节点在环时怎么处理。

次要维护两种操作:
op0:每次dfs时,进行一些初始化。注意这里不一定是入度为0的点。
op3:在第一次找到基环树的环的时候,从入口退出时怎么处理,一般没用。

下面是一种示例,必须是内向基环树,注意内向基环树的dfs上面有好几个时点:

时点0、进入环的时候,有时是从入度为0的点进入可能会有特殊操作,但是一般来说进入的时候主要是各个操作的初始化值。
时点1、当 color[u] != 0 && color[u] == c 时,重复找到了本次的dfs进入环的入口,可以这时候处理入口的值,但一般只交给时点3去做就好了。
时点2、当 color[u] != 0 && color[u] != c 时,找到了以前的dfs找过的点,有可能是环的其中一个入口,也有可能是普通的树分叉,因为不是从入度为0的点开始找的甚至可能本身是一条链,这个时候处理不在环中的操作(op1)。
时点3、当 incirle != 0 时,意味着在环中,处理在环中的操作(op2)。当 u==incirle 时,从环的入口退出,把在环中的标记清空,并处理有可能需要的退出环的操作op3,但是不见得大家都是在这里退出的啊,前面的每个点都有退出的机会的
时点4、以上都不是,意味着不在环中,处理不在环中的操作(op1)。

总之大概是这个样子,基环树也并不是都要存入度的,很多情况是可以直接用op1来继承,而且op1是躲不开的,因为有时候树会分叉。

const int MAXN = 2e5;

int n, G[MAXN + 5];
int color[MAXN + 5], cntcolor;

int incircle;
void dfs(int u, int c) {
    if(color[u]){
        if(color[u] == c){
            incircle = u;
            return;
        }
        //op1
        return;
    }
    color[u] = c;
    dfs(G[u], c);
    if(incircle) {
        //op2
        if(u == incircle) {
            //op3
            incircle = 0;
        }
    }
    //op1
}

void Test_case() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &G[i]);
    cntcolor = 0;
    for(int i = 1; i <= n; ++i) {
        if(!color[i]) {
            ++cntcolor;
            //op0
            dfs(i, cntcolor);
        }
    }
}

但是还是希望使用缩点法,缩点法没有这么多时点,全部都是建新图。

原文地址:https://www.cnblogs.com/KisekiPurin2019/p/11980305.html