tarjan_算法

更新：vector 存边板子

SCC：

void d(int x) {
    dfn[x]=low[x]=++tot;
    s[++t]=x;in[x]=1;
    for(int v:G[x]) {
        if(!dfn[v]) d(v),low[x]=min(low[x],low[v]);
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x]) {
        ++ct;
        while(in[x]) {
            col[s[t]]=ct;
            in[s[t--]]=0;
        }
    }
}

E-BCC：

void d(int x,int e) {
    dfn[x]=low[x]=++tot;
    s[++t]=x;
    for(auto[v,i]:G[x]) if(i^e) {
        if(!dfn[v]) d(v,i),low[x]=min(low[x],low[v]);
        else low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x]) {
        ++ct;
        while(s[t+1]!=x) {
            V[ct]+=s[t];
            col[s[t--]]=ct;
        }
    }
}

V-BCC：

void d(int x) {
    dfn[x]=low[x]=++tot;
    s[++t]=x;
    for(int v:G[x]) {
        if(!dfn[v]) {
            d(v),low[x]=min(low[x],low[v]);
            if(low[v]==dfn[x]) {
                ++ct;H[ct]+=x;
                while(s[t+1]^v) {
                    H[ct]+=s[t--];
                }
            }
        }
        else low[x]=min(low[x],dfn[v]);
    }
}

注意孤立点也是点双，需要特判。

自环不影响点双性，但会影响这个算法，需要去掉自环边。

8.5 专题 图连通性 强连通 点双边双 圆方树

点双的本质：边点互换后等价于原图边的边双，所以我们要把边划分成不同的集合。

T1 P7251 [JSOI2014] 强连通图

如何把一个图变成强连通图？

先缩点，然后统计入度 0，出度 0 的个数，取一个 $\max$。

这样做为什么是对的？

可以想象成一个二分图匹配，把入度 0 点视为左部点，出度为 0 视为右部点，每个左部点至少能到达一个右部点，问至少多少条边使得二分图强连通。

肯定是右部点往左部点连边，并且每个右部点都要连边，每个左部点都要被连，在此基础上可以证明 $\max(n_1,n_2)$ 条有向边即可。

T2 DAG上DP

首先缩 SCC，为了方便假设原 $1$ 号节点的新编号还是 $1$。

我们 $DP$ 处理出每个点到 $1$ 的最长路 $g$，和从 $1$ 出发的最长路 $f$，这个不需要建反图，由于在求 $g$ 意义下每个点只知道它的转移前驱，在求 $f$ 意义下每个点只知道他的转移后继，那么只需要求 $f$（拓扑序上）正序枚举刷表法，求 $g$ 倒序枚举填表法。

你甚至不需要topusort，因为缩 SCC 后编号就是拓扑序反序，所以上面的正序倒序再互换一下。

处理出来后答案就是枚举每条边反向，这条边反向的答案就是 $f_v+g_u-siz_1$（因为 $siz_1$ 多算了一遍）。

本来 DP 除了枚举顺序还是有些细节的，比如最后的反向边必须在拓扑序上“跨过”$1$，还有枚举端点不应该枚举不合法点以产生奇怪转移。

但是我发现这个图甚至不保证联通。

越来越麻烦了。

但是我们可以对 DP 初值进行处理，只有 $f_1=g_1=siz_1$，剩余初始都为 $-\infty$，这样那些细节就不用考虑了。

void dp(int st) {
    set(f,-0x3f);set(g,-0x3f);f[st]=g[st]=siz[st];
    UF(x,ct,1) G(i,x) f[v[i]]=max(f[v[i]],f[x]+siz[v[i]]);
    F(x,1,ct) G(i,x) g[x]=max(g[x],g[v[i]]+siz[x]);
    F(i,1,cnt) ans=max(ans,g[u[i]]+f[v[i]]-siz[st]);
}

T3 P3627 [APIO2009] 抢掠计划

裸的 DAG 上简单 DP。

有一个问题是：起点不是入度为 $0$ 怎么办？

正常搞，只让起点 DP 值有意义即可。

张老师给了另一种神奇的方法：缩点的时候以起点为根开始搜，这样得到的 DAG 没有起点不能到达的那部分，起点就是唯一的入度 $0$ 的点。

T4 图变边双

答案就是 $\lceil\frac{\sum_i[d_i==1]}{2}\rceil$，$d_i$ 是点 $i$ 的度数。

证明显然。

T5 ACwing397 逃不掉的路

就是求两点间有多少一定要经过的边。

就是边双树上两点距离。

T6 路径必经点

补充一下圆方树定义。

圆方树是在原图的点集的基础上添加一些点形成的一棵树，原图中的点成为圆点，添加的点称为方点，每条边连接一个圆点和方点，方点是每个点双的代表，方点向点双中的所有点连边。

可以去网上找个图来形象理解。

如何判断一个点是圆点还是方点？

发现叶子一定是圆点，然后黑白染色即可。

不过这样挺 sb 的，编号大于 $n$ 的是方点。

注意多测树剖的son[]要清空，tarjan的dfn要清空，top要清零，因为会留一个点在里面。

T7 U230731 [BJOI2013] 压力

简单圆方树上差分。

T8 一九八四 不知道是哪里的题

首先如何判断一个点能否作为割点割掉另一个点？

只判这个点是不是割点不行，因为任何一个点被割掉都算割点。

实际判断方法比判割点还简单，只需要看是否low[x]>=dfn[y]。

一条边能否作为割边？类似的，看是否low[x]>dfn[y]（x在dfs树上在y的下面）。

所以这个题只需要建出dfs树，然后分讨即可，不是特别麻烦。

struct T {
    int cnt=1,u[M],v[M],Next[M],start[N];
    int dfn[N],fa[N],tot,dfx[N],siz[N],son[N],dep[N],top[N];
    void add(int x,int y) {fa[y]=x;v[++cnt]=y;Next[cnt]=start[x];start[x]=cnt;}
    void d(int x) {
        dep[x]=dep[fa[x]]+1;siz[x]=1;
        G(i,x) d(v[i]),siz[x]+=siz[v[i]],siz[son[x]]<siz[v[i]]&&(son[x]=v[i]);
    }
    void d(int x,int tp) {
        top[x]=tp;dfn[x]=++tot;dfx[tot]=x;
        if(son[x]) d(son[x],tp);
        G(i,x) if(v[i]^son[x]) d(v[i],v[i]);
    }
    int lca(int x,int y) {
        while(top[x]^top[y]) {
            x=fa[top[dep[top[x]]<dep[top[y]]?x^=y^=x^=y:x]];
        } return dep[x]<dep[y]?x:y;
    }
    int jmp(int x,int d) {
        while(dep[x]-dep[fa[top[x]]]<=d) d-=dep[x]-dep[fa[top[x]]],x=fa[top[x]];
        return dfx[dfn[x]-d];
    }
    int dis(int x,int y) {return dep[x]+dep[y]-2*dep[lca(x,y)];}
    bool in(int x,int a) {return dfn[x]>=dfn[a]&&dfn[x]<dfn[a]+siz[a];}
    bool in(int x,int a,int b) {return dis(a,x)+dis(b,x)==dis(a,b);}
    bool q(int a,int b,int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        if(fa[x]^y) return 1;
        bool i1=in(a,x),i2=in(b,x);
        if(i1&&i2) return 1;
        if(!i1&&!i2) return 1;
        return ge(x,y)?0:1;
    }
    bool q(int a,int b,int x) { 
        if(!in(x,a,b)) return 1;
        bool i1=in(a,x),i2=in(b,x);
        if(!i1&&!i2) return 1;
        if(i1&&i2) {
            int l=lca(a,b);if(l^x) return 1;
            if(gd(jmp(a,dep[a]-dep[x]-1),x)|gd(jmp(b,dep[b]-dep[x]-1),x)) return 0; else return 1;
        } else {
            if(i1) return gd(jmp(a,dep[a]-dep[x]-1),x)?0:1;
            else return gd(jmp(b,dep[b]-dep[x]-1),x)?0:1;
        } return 114514&1;
    }
} t;

此代码还顺便描述了树剖跳固定常数单位的方法。

注意封装的过程判断割点和割边调用的dfn不要调用成树剖的dfn了。

T9 CF487E Tourists

*3200。

但感觉不是特别难。

问无向图中一个点到另一个点的所有路径上点的最小权值，带修改权值。

手模几组数据会发现其实就是把圆点的权值挂在相邻方点上，查询就是链 $\min$。

那修改咋办呢？

7.10 那场比赛涉及了树上毛毛虫修改，链询问，思路是对一个点的修改对父亲的影响暴力修改，对儿子的影响记在自己身上，然后按轻重边考虑。

那本题有没有什么更简单的写法呢？

我们发现，本题是求 $\min$，而 $\min$ 的性质就要好一些，可以不用轻重边考虑，只要统计一个方点，那他的父亲就一定会被统计上（特判lca处），所以每个方点开一个std::multiset，若方点的儿子被改，那么就改set中的值更新该点的权值，如果父亲被改，由于父亲有很多方点儿子，我们直接把修改设为父亲的权值，这样链 $\min$ 的时候自然会统计到父亲。

P8867 [NOIP2022] 建造军营

给定无向图，任意选点集 $V$，并选择边集 $E$ 保护，满足删除任意一条非保护边点集仍联通，求选择的方案数。

$n\le 5\times 10^5$。

首先发现一个边双内的边是无所谓是否保护的，所以首先缩边双，设 $V_x,E_x$ 为 $x$ 节点在原图中的点数、边数。

考虑边双树上 $\text{dp}$，考虑你需要关心什么，你发现被保护的点集一定是一个连通块，你需要关心这个子树内选没选点对吧。

设 $f_{x,0/1}$ 表示 $x$ 子树内没选/选点的方案数，但你发现一个比较严重的问题，你不会处理 $f_{x,0}\cup f_{v,1}$，因为你不太知道 $v\to x$ 是不是任意选择，假如强制选/不选，那并不好统计答案，但如果两种情况都算上，在 $f_{x,1}\cup f_{v,1}$ 的时候我们就不知道有多少边我们忘记强制选上了。

更改状态：$f_{x,0/1}$ 表示 $x$ 子树内没选/选了的方案数，但如果选了点，则必须用边和 $x$ 联通，$x$ 本身可选可不选。

$$(f_{x,0},f_{x,1})=(2^{E_x},2^{E_x}(2^{V_x}-1)),(f_{x,0},f_{x,1})\gets(2f_{x,0}f_{v,0},2f_{x,1}f_{v,0}+f_{x,1}f_{v,1}+f_{x,0}f_{v,1})$$

统计答案考虑在每种方案的连通块最上端统计，但你发现如果你只选了一个点，它可以一直往上选边延伸，所以你还需要钦定 $f_{x,1}$ 这个状态的 $x\to fa_x$ 一定不选，$1$ 号点需要特判。

$$ans\gets f_{x,1}+\sum_{x\ne 1}f_{x,1}2^{m-\sum_{v\in x} E_v-1}$$

P9167 [省选联考 2023] 城市建造

给定无向连通图，询问有多少边集非空子图满足删去 $E$ 中恰好形成 $|V|$ 个连通块，且这些连通块的大小之差不超过 $k\in[0,1]$。

$n\le 10^5$。

考虑挖掘一些性质。

由于恰形成 $|V|$ 个联通块，说明每个点在且仅在一个连通块中，且除了选择的点外这些连通块间不能有路径。

可以得出一个点双中如果选了超过两个点那么整个点双都要选，否则由于点双连通，这两个点之间的边删去后仍能通过点双来联通。

还有就是两个被选点之间的路径一定全选，这是因为不能有路径连接这两个连通块。

建出圆方树，考虑 $\text{dp}$。

首先考虑 $k=0$，你发现这种情况下每个连通块的大小确定了那么划分方案 $\le 1$，构造就是自下而上剥掉子树，所以我们首先枚举连通块大小 $d\in d(n)$。

考虑这个划分十分平均，那么以（圆点为权的带权）重心为根，许多情况下以重心为根都有很优秀的性质。

如果要删点双，删掉的点双一定是与根相连的连通块，即方点被选则该点的方点祖先一定被选。

设 $f_x$ 对方点来说它表示自己是否被删，这事实上可以被子树中圆点的个数（设为 $\text{siz}_x$）唯一决定：$f_x=[\text{siz}_x\ge d]$，$\text{siz}_x=d$ 的时候如果不删这个方点的话就会拉上 $fa_x$ 这个圆点，就非法了。

把方点挂在 $\text{siz}_x$ 上并查集维护 $\text{cnt}_i$ 表示大小为 $i$ 的连通块的个数即可 $\Theta(n)$。

接着考虑 $k=1$，我们考虑能否故技重施，先求出所有连通块大小 $\in\{d,d+1\}$ 的方案和，再减去求了两遍的连通块大小仅为 $d$ 的方案，不难发现后者就是 $k=0$ 的情况。

显然 $\text{siz}_x\ge d+1$ 时必须被删，$\text{siz}_x<d$ 时不能被删，而 $\text{siz}_x=d$ 时我们称它为特殊态，它们处于摇摆阶段，可以接受一个父亲的加入，但最多只能接受一个。

我们发现，对于一个有若干个特殊态儿子的圆点，若该节点有 $\text{siz}<d$ 的儿子，那么一个特殊态儿子也不能保留，否则还可以选择 $\le 1$ 个特殊态儿子保留，这也是本题 $\bmod \ 998244353$ 唯一需要的地方。

注意一个特殊态方点若有两个儿子则其不能删掉，出现了矛盾的话需要判掉。

在实际的操作中可以融入 $k=0$ 的判断之中，因为我们发现 $\text{siz}_x=d$ 时对于特殊点只有一个儿子就删掉，有多个儿子就不删就可以判断它的合法性，我们同时发现 $k=0$ 时该操作也可以维护合法性，所以我们在两种方案中都使用这种方案判断是比较简洁的。

一个小细节：$k=1\wedge d>1$ 时只有一个儿子的特殊态点的父亲如果是孤身一人，要把这个儿子与父亲连通起来。

判完了合法性，方案数就是所有（作为一个特殊态点的父亲 $\wedge$ 没有 $\text{siz}<d$ 的儿子 $\wedge$ 没有有多个儿子的特殊态儿子）的圆点的（特殊态儿子个数 $+1$）的乘积。

但还有一个地方，这些情况不一定全合法，要判掉 $d>1$ 且全删掉的情况，这种情况留根孤零零一个就不合法了。

考虑特殊态点是均摊 $\Theta(1)$ 的，所以可以暴力枚举特殊态点求出其父亲。