连通性
参考资料
强连通分量（SCC）
强连通分量（Strongly Connected Component，SCC）是有向图的极大子图，其中任意两点互相可达。把每个 SCC 缩成一点后，原图变为有向无环图（DAG）。
Tarjan 算法
Tarjan 用一次 DFS 求出所有 SCC。 为 的 DFS 序， 为 经搜索树边及至多一条返祖边能到达的最小 。DFS 时把点压栈，当 时，栈中 及其上方的点构成一个 SCC。时间复杂度为 。
vector<int> G[N];
int dfn[N],low[N],sccno[N];
int cnt=0,scc_cnt=0;
stack<int> s;
void tarjan(int u)
{
low[u]=dfn[u]=++cnt;
s.push(u);
for(auto v:G[u])
{
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!sccno[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scc_cnt++;
while(1)
{
int x=s.top();
s.pop();
sccno[x]=scc_cnt;
if(x==u)break;
}
}
}
双连通分量（BCC）
无向图的 双连通分量 分两种：边双连通分量（删去任意一条边后仍连通）与 点双连通分量（删去任意一个点后仍连通）。两者都借助 Tarjan 的 求出。
边双连通分量
边双内任意两点间存在两条无公共边的路径。求法：Tarjan 时不沿来时的边返回（用边编号 区分重边）， 时弹栈得到一个边双。满足 的边 即为桥。
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
vector<pair<int,int>> G[N];
int dfn[N],low[N],bccno[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
void tarjan(int u,int k)
{
low[u]=dfn[u]=++cnt;
s.push(u);
for(auto [v,i]:G[u])
{
if(!dfn[v])
{
tarjan(v,i);
low[u]=min(low[u],low[v]);
}
else if(i!=k)
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
bcc_cnt++;
while(1)
{
int x=s.top();
s.pop();
bccno[x]=bcc_cnt;
if(x==u)break;
}
}
}
vector<int> ans[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back({v,i});
G[v].push_back({u,i});
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i,-1);
}
for(int i=1;i<=n;i++)
{
ans[bccno[i]].push_back(i);
}
cout<<bcc_cnt<<'\n';
for(int i=1;i<=bcc_cnt;i++)
{
cout<<ans[i].size()<<' ';
for(auto x:ans[i])cout<<x<<' ';
cout<<'\n';
}
return 0;
}
点双连通分量
点双内任意两点间存在两条除端点外无公共点的路径。求法：DFS 中当子节点 满足 时，把栈中直到 的点连同 一起取出，构成一个点双；孤立点单独算一个点双。
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
vector<int> G[N];
int dfn[N],low[N];
int cnt=0,bcc_cnt=0;
stack<int> s;
vector<int> ans[N];
void tarjan(int u,int fa)
{
low[u]=dfn[u]=++cnt;
s.push(u);
int son=0;
for(auto v:G[u])
{
if(!dfn[v])
{
son++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
bcc_cnt++;
while(1)
{
int x=s.top();
s.pop();
ans[bcc_cnt].push_back(x);
if(x==v)break;
}
ans[bcc_cnt].push_back(u);
}
}
else if(v!=fa)
{
low[u]=min(low[u],dfn[v]);
}
}
if(fa==0&&son==0)ans[++bcc_cnt].push_back(u);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])tarjan(i,0);
}
cout<<bcc_cnt<<'\n';
for(int i=1;i<=bcc_cnt;i++)
{
cout<<ans[i].size()<<' ';
for(auto x:ans[i])cout<<x<<' ';
cout<<'\n';
}
return 0;
}
割点和桥
割点（cut vertex）是删去后使连通分量增多的点，桥（bridge）是删去后使连通分量增多的边。用 Tarjan 求割点：非根节点 若存在子节点 满足 ，则 为割点；根节点当且仅当它在搜索树中有至少两棵子树时为割点。
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int> G[N];
int dfn[N],low[N],cnt=0;
bool cut[N];
void tarjan(int u,int rt)
{
dfn[u]=low[u]=++cnt;
int son=0;
for(auto v:G[u])
{
if(!dfn[v])
{
tarjan(v,rt);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=rt)cut[u]=1;
if(u==rt)son++;
}
else low[u]=min(low[u],dfn[v]);
}
if(u==rt&&son>=2)cut[u]=1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);
vector<int> res;
for(int i=1;i<=n;i++)if(cut[i])res.push_back(i);
cout<<res.size()<<'\n';
for(auto x:res)cout<<x<<' ';
cout<<'\n';
return 0;
}
圆方树
圆方树 把无向图的点双连通分量结构转化为一棵树：原图的点为「圆点」，每个点双新建一个「方点」连向其中所有圆点。原图上与两点间路径相关的问题，在圆方树上变成树上路径问题，常用于处理仙人掌（每条边至多在一个环上的图）。
2-SAT
SAT 即布尔可满足性（Satisfiability）问题。-SAT 在 时是 NP 完全的，OI 中只研究 的 2-SAT：给定 个布尔变量与若干形如「 或 」的约束，求一组可行赋值。
把每个变量拆成「真」「假」两个节点。约束「 或 」等价于两条蕴含边：若 则必有 ，若 则必有 。对蕴含图跑 Tarjan 求 SCC：若某变量的真、假节点落在同一 SCC 则无解；否则每个变量取 SCC 编号较小（拓扑序较后）的节点对应的值，即为一组可行解。
#include <bits/stdc++.h>
using namespace std;
const int N=2000005;
vector<int> G[N];
int dfn[N],low[N],sccno[N],cnt=0,scc_cnt=0;
stack<int> s;
bool ins[N];
void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
s.push(u);ins[u]=1;
for(auto v:G[u])
{
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
scc_cnt++;
while(1)
{
int x=s.top();s.pop();ins[x]=0;
sccno[x]=scc_cnt;
if(x==u)break;
}
}
}
int n,m;
int f(int i,int v){return v?i:i+n;}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
while(m--)
{
int a,va,b,vb;
cin>>a>>va>>b>>vb;
G[f(a,1-va)].push_back(f(b,vb));
G[f(b,1-vb)].push_back(f(a,va));
}
for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
if(sccno[i]==sccno[i+n])
{
cout<<"IMPOSSIBLE"<<'\n';
return 0;
}
}
cout<<"POSSIBLE"<<'\n';
for(int i=1;i<=n;i++)cout<<(sccno[i]<sccno[i+n])<<' ';
cout<<'\n';
return 0;
}