联通性这东西学一次忘一次，只能背板子了。

原理？太困难了算了吧，板子也不难背。

真想学原理去网上找找别的博客吧。

考 tarjan 原理就爆了。

还有，tarjan 的复杂度是 $O(n+m)$ 的。

模板

求割边模板

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int> 
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10;
int n,m,cnt=1,ans,tim;
int head[maxn];
int dfn[maxn],low[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
vector<pii> g;
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void tarjan(int u,int eid){
    dfn[u]=low[u]=++tim;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) g.push_back({u,v});
        }
        else if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v),add(v,u);
    for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
    sort(g.begin(),g.end());
    for(auto x:g) cout<<x.fi<<" "<<x.se<<'\n';
    return 0;
}

求割点模板

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10,maxm=1e5+10;
int n,m,cnt,tim,ans;
int head[maxn];
int dfn[maxn],low[maxn];
bitset<maxn> cut;
struct node{
    int to,nxt;
}e[maxm<<1];
vector<int> g;
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void tarjan(int u,int fa){
    int son=0;
    dfn[u]=low[u]=++tim;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            ++son;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(u!=fa&&low[v]>=dfn[u]) g.push_back(u);
        }
        else if(v!=fa) low[u]=min(low[u],dfn[v]);
    }
    if(u==fa&&son>=2) g.push_back(u);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v),add(v,u);
    for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    for(auto x:g) cout<<x<<'\n';
    return 0;
}

缩点模板

#include"bits/stdc++.h"
#define re register
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e5+10,maxm=1e5+10;
int n,m,cnt,top,tim,scc;
int head[maxn];
int dfn[maxn],low[maxn],stk[maxn];
int col[maxn],f[maxn];
int in[maxn];
bitset<maxn> vis;
vector<pii> g;
struct edge{
    int to,nxt;
}e[maxm];
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++tim;
    stk[++top]=u,vis[u]=1;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scc;int x;
        do{
            x=stk[top--];
            col[x]=scc;
            vis[x]=0;
        }while(x!=u);
    }
}
inline void clear(){
    cnt=0;
    memset(head,0,sizeof head);
}
inline void topo(){
    queue<int> q;
    for(re int i=1;i<=scc;++i) if(!in[i]) q.push(i);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(re int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(!(--in[v])) q.push(v);
            //do something here
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v),g.push_back({u,v});
    for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    clear();
    for(auto x:g) if(col[x.fi]!=col[x.se]) add(col[x.fi],col[x.se]),++in[col[x.se]];
    topo();
    return 0;
}

求点双模板

#include"bits/stdc++.h"
using namespace std;
#define re register
#define int long long
const int maxn=5e5+10,maxm=2e6+10;
int n,m,cnt,tot,top,tim;
int head[maxn];
int dfn[maxn],low[maxn];
int stk[maxn];
bitset<maxn> vis;
vector<int> g[maxn];
struct edge{
    int to,nxt;
}e[maxm<<1];
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void tarjan(int u,int fa){
    int son=0;
    dfn[u]=low[u]=++tim;
    stk[++top]=u;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            ++son;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                ++tot;int x;
                g[tot].push_back(u);
                do{
                    x=stk[top--];
                    g[tot].push_back(x);
                }while(x!=v);
            }
        }
        else if(v!=fa) low[u]=min(low[u],dfn[v]);
    }
    if(u==fa&&!son) g[++tot].push_back(u);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v),add(v,u);
    for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
    cout<<tot<<'\n';
    for(re int i=1;i<=tot;++i){
        cout<<g[i].size()<<" ";
        for(auto j:g[i]) cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}

求边双模板

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=5e5+10,maxm=2e6+10;
int n,m,cnt=1,tot,tim;
int head[maxn];
int dfn[maxn],low[maxn];
int col[maxn];
bitset<maxm<<1> vis; 
vector<int> g[maxn];
struct edge{
    int to,nxt;
}e[maxm<<1];
inline void add(int u,int v){
    e[++cnt]={v,head[u]};
    head[u]=cnt;
}
inline void tarjan(int u,int eid){
    dfn[u]=low[u]=++tim;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) vis[i]=vis[i^1]=1;
        }
        else if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
    }
}
inline void dfs(int u,int id){
    col[u]=id;
    g[id].push_back(u);
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(col[v]||vis[i]) continue;
        dfs(v,id);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(re int i=1,u,v;i<=m;++i) cin>>u>>v,add(u,v),add(v,u);
    for(re int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
    for(re int i=1;i<=n;++i){
        if(!col[i]) dfs(i,++tot);
    }
    cout<<tot<<'\n';
    for(re int i=1;i<=tot;++i){
        cout<<g[i].size()<<" ";
        for(auto j:g[i]) cout<<j<<" ";
        cout<<'\n';
    }
    return 0;
}

常见技巧

有一些无向图上的问题需要先缩个点/边双然后变成树上问题。

有一些有向图上的问题需要先缩个点然后变成 DAG，然后拓扑序上搞事情。

但一般来说难点都在缩完以后搞得那些东西上，例如 dp，贪心，数据结构啥的。

点不能重复：缩点双。一条边最多属于一个点双。

边不能重复：缩边双。一个点最多属于一个边双。

所以把环缩成点要缩边双。

例题

下面选的基本都是一些简单板子题。

间谍网络

缩点板子。

首先判断无解，然后缩点，然后把入度为 0 的点的权值拿了就行。

一个强连通分量构成的点的权值为其内所有点的最小权值。

有机化学之神偶尔会做作弊

把环缩成点要缩边双。

然后变成一颗树，树上距离随便求。

[USACO5.3] 校园网Network of Schools

首先缩点，那么第一问答案就是入度为 0 的点的个数（和上面那个题一样）。

第二问要求最少加几条边使得 DAG 变成强连通。

我们贪心的想，肯定要让无出度点连向无入度点。那么连的边数就是 $\max(无出度点,无入度点)$。

注意特判本来就是强连通的情况。

采蘑菇

缩点以后变为 DAG 上最长路，dp 一下即可。

[USACO06JAN] Redundant Paths G

经典结论题。

求最少添加多少条边，使得图变成边双连通。

缩完点双后，统计入度和出度，答案为：（入度和出度之和为 1 的点+1）/2

正则表达式

板子。

强连通分量内部不需要价值，所以缩点以后 DAG 上最短路即可。

[APIO2009] 抢掠计划

板子。

强连通分量显然可以全拿，缩点以后 DAG 上最长路即可，注意只能在是酒吧的点取答案。

[Wind Festival] Running In The Sky

板子。

缩点以后 DAG 上最长路即可，注意还得求个最大值。

[SDOI2010] 所驼门王的宝藏

怎么降蓝了？在 WLFS 做的时候还是紫。

如果图建好了，那么它是板子，缩点以后 DAG 上最长路即可。

但难点就在建图。

直接建是 $O(n^2)$ 的，肯定不行。

但是每一行的横门可以相互到达，每一列的纵门也可以相互到达。

对于优化建边有个常见套路：建虚点，然后把边都连向虚点。

这样边数就是 $O(n)$ 的了。

[NOIP2022] 建造军营

边双缩点后树形 dp。

但是我不会这个 dp。

摆。

[POI2008] BLO-Blockade

分情况讨论。

若 $u$ 不是割点，那么它会和剩下 $n-1$ 个点不连通。

若 $u$ 是割点，那么显然会得到若干联通块（$u$ 这个点自己也算个连通块）。

那么答案就是 $2\sum_{i=1}^k siz_i\times (n-siz_i)$。

求割点时顺便统计一下子树大小即可。

[HAOI2010] 软件安装

缩点以后变成树形背包板子。

为什么缩完是树？因为题目保证只依赖一个物品。

[USACO04DEC] Cow Ski Area G

把图建出来以后就是[USACO5.3] 校园网Network of Schools 的第二问。

「TAOI-1」椎名真昼

好玩的博弈论。

先不考虑博弈，只看这张图能不能全变白，可以发现：如果一个强连通分量里有异色点，那就不能。

所以可以先缩点，顺便判断无解，此时我们得到一张 DAG。

如果你思考一会，会发现这个游戏是很难有人获胜的。

除非一步就能赢，否则对方可以一直模仿你的操作使你赢不了。

所以可以猜到：只有一步能赢的时候才有人能赢，否则平局。

那么考虑怎么一步赢。

Alice 是很好考虑的，因为只能操作一次，所以如果遇到一个黑点，那么往后走就不能出现白点。

如果搜完以后有没搜到的黑点，那么就寄了。

Bob 比较复杂。

1. 若存在至少一个入度为 0 的点为白点，那么 Bob 获胜当且仅当所有点都是白点。因为 Alice 可以让其中一个点变黑，Bob 为了赢必须把这个点弄回来。
2. 若所有入度为 0 的点均为黑点，如果只有一个那 Alice 肯定赢。如果有两个，那 Bob 肯定赢。否则平局。
3. 只有两个点，一黑一白，且黑点指向白点，则 Bob 必胜。

综上，Bob 必胜的情况共三种：

1. 两个孤立黑点。
2. 两个点，一黑一白，且黑点指向白点。
3. 所有点均为白点。

「EVOI-RD2」旅行家

因为边不可以重复经过，所以缩边双。

变成一棵树后就很简单了，每次覆盖一条路径，求被覆盖过的点的点权和。

事实上都不用树剖，树上差分即可。