笔记 算法 从 tarjan 到圆方树
强连通
强连通分量：在一张有向图中，如果 $u$ 能走到 $v$，$v$ 能走到 $u$，那么 $u,v$ 在同一个强连通分量内。
求强连通分量
强连通分量缩点：将一张有向图中所有在同一个强连通分量内的点变成同一个点。缩点之后是拓扑图。
另外，拓扑序实际上就是缩点之后的逆序，所以无需再写拓扑排序。
必须注意 vis 数组是必须的，不可用 bel 数组代替，尽管那样子可以通过洛谷模板。
P3387 【模板】缩点
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=1e4+7;
int n1,m,dc,n2,low[N],dfn[N],bel[N],vis[N];
int w[N],val[N],f[N];
vector<int>g1[N],g2[N];
stack<int>s;
void tar1(int u){
low[u]=dfn[u]=++dc;
s.push(u);vis[u]=true;
for(int v:g1[u])
if(!dfn[v])tar1(v),low[u]=min(low[u],low[v]);
else if(vis[v])low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){
bel[u]=++n2;vis[u]=false;
for(;s.top()!=u;s.pop())bel[s.top()]=n2,vis[s.top()]=false;
s.pop();
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n1>>m;
for(int i=1;i<=n1;i++)
cin>>w[i];
for(int i=1,u,v;i<=m;i++)
cin>>u>>v,g1[u].push_back(v);
for(int i=1;i<=n1;i++)
if(!dfn[i])tar1(i);
for(int i=1;i<=n1;i++){
val[bel[i]]+=w[i];
for(int v:g1[i])if(bel[i]!=bel[v])
g2[bel[i]].push_back(bel[v]);
}
for(int i=n2;i>=1;i--){
f[i]+=val[i];
for(int v:g2[i])
f[v]=max(f[v],f[i]);
}
cout<<*max_element(f+1,f+1+n2);
return 0;
}
2-SAT
给定若干约束条件：「如果 $x=0/1$，那么 $y=0/1$」，问你是否存在解。
不妨学习种类并查集，把点 $x$ 作为命题 $x=1$，点 $x+n$ 作为命题 $x=0$，如果命题 $A$ 能推出命题 $B$ 则连边 $A\to B$。
对该图进行强连通分量缩点，如果缩点后 $x$ 与 $x+n$ 在同一个连通内则无解。否则，两个点的拓扑序必然不同，令拓扑序较大的那个命题成立即可。
P4782 【模板】2-SAT
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=2e6+7;
int n,m,dc,cnt,low[N],dfn[N],bel[N],vis[N];
basic_string<int>g[N];
stack<int>s;
void tar1(int u){
low[u]=dfn[u]=++dc;
s.push(u);vis[u]=true;
for(int v:g[u])
if(!dfn[v])tar1(v),low[u]=min(low[u],low[v]);
else if(vis[v])low[u]=min(low[u],dfn[v]);
if(low[u]==dfn[u]){
bel[u]=++cnt;vis[u]=false;
for(;s.top()!=u;s.pop())bel[s.top()]=cnt,vis[s.top()]=false;
s.pop();
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i=1,x,a,y,b;i<=m;i++){
cin>>x>>a>>y>>b;
g[x+n*a].push_back(y+n*!b);
g[y+n*b].push_back(x+n*!a);
}
for(int i=1;i<=2*n;i++)
if(!dfn[i])tar1(i);
for(int i=1;i<=n;i++)
if(bel[i]==bel[i+n])return cout<<"IMPOSSIBLE\n",0;
cout<<"POSSIBLE\n";
for(int i=1;i<=n;i++)
cout<<(bel[i]<bel[i+n])<<' ';
return 0;
}
边双连通分量
边双连通分量：在一张无向图中，如果任意删去一条边后 $u,v$ 仍然连通，那么 $u,v$ 在同一个边双连通分量内。
求边双连通分量
割边（桥）：在一张无向图中，如果删去某条边之后图的连通块数量发生了改变，那么这条边是桥。
边双连通分量缩点：将一张无向图中所有在同一个边双连通分量内的点变成同一个点。边双连通分量缩点之后是树，并且树上的每条边都是割边。
在有重边的时候，可以记录每条边的编号来区分重边。
P8436 【模板】边双连通分量
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=5e5+7;
int n,m,dc,low[N],dfn[N];
vector<vector<int>>res;
vector<pii>g[N];
stack<int>s;
void tar2(int u,int id){
low[u]=dfn[u]=++dc;
s.push(u);
for(auto[v,w]:g[u])if(w!=id){
if(!dfn[v])tar2(v,w),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
// 形成一个边双，割边就是 (x,fa)
auto&b=res.emplace_back();
for(;s.top()!=u;s.pop())b.push_back(s.top());
b.push_back(s.top());s.pop();
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
g[u].emplace_back(v,i);
g[v].emplace_back(u,i);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tar2(i,0);
cout<<siz(res)<<'\n';
for(const auto&i:res){
cout<<siz(i)<<' ';
for(int j:i)cout<<j<<' ';
cout<<'\n';
}
return 0;
}
点双
点双连通分量：在一张无向图中，如果任意删去一个非 $u,v$ 的点后 $u,v$ 仍然连通，那么 $u,v$ 在同一个点双连通分量内。
求点双连通分量
P8435 【模板】点双连通分量
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=5e5+7;
int n,m,dc,low[N],dfn[N];
vector<vector<int>>res;
vector<int>g[N];
stack<int>s;
void tar3(int u,int fa){
low[u]=dfn[u]=++dc;
s.push(u);
for(int v:g[u])if(v!=fa){
if(!dfn[v]){
tar3(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
auto&b=res.emplace_back();
for(;s.top()!=v;s.pop())b.push_back(s.top());
s.pop();b.push_back(u);b.push_back(v);
}
}else low[u]=min(low[u],dfn[v]);
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
if(u!=v)g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i]){
tar3(i,0);
if(!siz(g[i]))res.push_back({i});
}
cout<<siz(res)<<'\n';
for(const auto&i:res){
cout<<siz(i)<<' ';
for(int j:i)cout<<j<<' ';
cout<<'\n';
}
return 0;
}
割点
割点：在一张无向图中，如果删去某个点之后图的连通块数量发生了改变，那么这个边是割点。当且仅当一个点在大于等于两个点双连通分量中出现时，这个点是割点。
P3388 【模板】割点（割顶）
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=5e5+7;
int n,m,dc,low[N],dfn[N],cnt[N];
vector<vector<int>>res;
vector<int>g[N];
stack<int>s;
void tar3(int u,int fa){
low[u]=dfn[u]=++dc;
s.push(u);
for(int v:g[u])if(v!=fa){
if(!dfn[v]){
tar3(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
auto&b=res.emplace_back();
for(;s.top()!=v;s.pop())b.push_back(s.top());
s.pop();b.push_back(u);b.push_back(v);
}
}else low[u]=min(low[u],dfn[v]);
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
if(u!=v)g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i]){
tar3(i,0);
if(!siz(g[i]))res.push_back({i});
}
for(const auto&i:res){
for(int j:i)cnt[j]++;
}
int ans=0;
for(int i=1;i<=n;i++)
ans+=(cnt[i]>=2);
cout<<ans<<'\n';
for(int i=1;i<=n;i++)
if(cnt[i]>=2)cout<<i<<' ';
return 0;
}
圆方树
圆方树：我们发现一个点如果是割点，那这个点会在多个点双连通分量中出现，所以不能直接缩点。
将所有在原图中的点称作圆点，不妨对于每个点双连分量，新开一个方点，把所有属于该点双连分量的点与其对应的方点连边，同时忽略原图中的所有点，就形成了一棵树，称作圆方树。
- 圆方树上的每一条边都连接了一个圆点和一个方点或者两个圆点。
- 连边大于等于二的圆点是割点，连边等于一的圆点是非割点。
- 一条从圆点到圆点的树上路径表示所有原图中这两个点形成的简单路径的并。
P4630 [APIO2018] 铁人两项
#include<bits/stdc++.h>
#define siz(x) int((x).size())
#define all(x) std::begin(x),std::end(x)
#define fi first
#define se second
using namespace std;
using unt=unsigned;
using loli=long long;
using lolu=unsigned long long;
using pii=pair<int,int>;
mt19937_64 rng(random_device{}());
constexpr int N=2e5+7;
int n1,m,n2,dc,cnt,dfn[N],low[N],sz[N];
loli ans;
stack<int>s;
vector<int>g1[N],g2[N];
void tar3(int u){
dfn[u]=low[u]=++dc;
s.push(u);cnt++;
auto add=[](int x,int y){
g2[x].push_back(y);
g2[y].push_back(x);
};
for(int v:g1[u]){
if(!dfn[v]){
tar3(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
n2++;
for(;s.top()!=v;s.pop())add(s.top(),n2);
s.pop();
add(n2,u);
add(n2,v);
}
}else low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int fa){
int val;
if(u<=n1)sz[u]=1,val=-1;
else sz[u]=0,val=siz(g2[u]);
for(int v:g2[u])if(v!=fa){
dfs(v,u);
ans+=2ll*sz[u]*sz[v]*val;
sz[u]+=sz[v];
}
ans+=2ll*sz[u]*(cnt-sz[u])*val;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n1>>m;n2=n1;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
g1[u].push_back(v);
g1[v].push_back(u);
}
for(int i=1;i<=n1;i++)if(!dfn[i]){
cnt=0;
tar3(i);
dfs(i,0);
}
cout<<ans;
return 0;
}