割边
对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图 \(G=\{V,E\}\)，e 是其中一条边（即 \(e \in E\)），如果 \(G-e\) 是不连通的，则边 \(e\) 是图 \(G\) 的一条割边（桥）。
割边判定法则
无向边 \((x,y)\) 是桥当且仅当搜索树上存在 \(x\) 的一个子节点 \(y\)，满足： \(dfn[x]<low[y]\)
#include<bits/stdc++.h>
using namespace std;
const int N=1110000;
struct edge{int x,y,pre;}a[N];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int id,dfn[N],low[N];
int bridge[N];
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++id;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y,k);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){//割边判定法则
bridge[k^1]=bridge[k]=1;
}
}
else if(k!=(in_edge^1)){//当前边不是入边的反边
low[x]=min(low[x],dfn[y]);
}
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
for(int i=2;i<=alen;i+=2){
if(bridge[i]){
printf("%d %d\n",a[i].x,a[i].y);
}
}
return 0;
}
割点
对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。
割点判定法则
若 \(x\) 不是搜索树的根节点（深度优先遍历的起点），则 \(x\) 是割点当且仅当搜索树上存在 \(x\) 的一个子节点 \(y\)，满足：\(dfn[x] \le low[y]\)
特别地，若 \(x\) 是搜索树的根节点，则 \(x\) 是割点当且仅当搜索树上存在至少两个子节点 \(y_1，y_2\) 满足上述条件。
#include<bits/stdc++.h>
using namespace std;
const int N=21100,M=211000;
struct edge{int x,y,pre;}a[M];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int id,dfn[N],low[N];
int root,cut[N];
void tarjan(int x){
dfn[x]=low[x]=++id;
int child=0;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
child++;
if(x!=root||child>1){
cut[x]=1;
}
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
alen=0;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i])root=i,tarjan(i);
}
int ans=0;
for(int i=1;i<=n;i++){
if(cut[i])ans++;
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
if(cut[i])printf("%d ",i);
}
return 0;
}
边双连通分量（e-DCC）
若一张无向连通图不存在割边，则称它“边双连通图”。
无向连通图的极大边双连通子图被称为“边双连通分量”，简记为 "\(e-DCC\)"。
定理：一张无向连通图是“边双连通图”，当且仅当任意一条边都包含在至少一个简单环中。
计算 \(e-DCC\) 只需求出无向图中所有的桥，把桥都删除后，无向图会分成若干个连通块，每一个连通块就是一个“边双连通分量”
#include<bits/stdc++.h>
using namespace std;
const int N=511000,M=4110000;
struct edge{int x,y,pre;}a[M];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int id,dfn[N],low[N];
int bridge[M];
int cnt,c[N];
vector<int>edcc[N];
void tarjan(int x,int in_edge){
dfn[x]=low[x]=++id;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y,k);
low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]){
bridge[k]=bridge[k^1]=1;
}
}
else if(k!=(in_edge^1)){
low[x]=min(low[x],dfn[y]);
}
}
}
void dfs(int x){
c[x]=cnt,edcc[cnt].push_back(x);
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(c[y]||bridge[k])continue;
dfs(y);
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
alen=1;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i,0);
}
for(int i=1;i<=n;i++){
if(!c[i]){
cnt++;
dfs(i);
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++){
printf("%d ",edcc[i].size());
for(int j=0;j<edcc[i].size();j++){
printf("%d ",edcc[i][j]);
}
puts("");
}
return 0;
}
e-DCC缩点
for(int k=2;k<=alen;k++){
int x=a[k].x,y=a[k].y;
if(c[x]!=c[y]){
add(c[x],c[y]);
}
}
点双连通分量（v-DCC）
若一张无向连通图不存在割点，则称它为“点双连通图”。
无向连通图的极大点双连通子图被称为“点双连通分量”，简记为 "\(v-DCC\)"。
定理：一张无向连通图是“点双连通图”，当且仅当满足下列两个条件之一。
1.图的顶点数不超过 \(2\)。
2.图中任意两点都同时包含在至少一个简单环中。
若某个点为孤立点，则它单独构成一个 "\(v-DCC\)"。除了孤立点之外，点双连通分量的大小至少为 \(2\)。
具体求法详见代码。
#include<bits/stdc++.h>
using namespace std;
const int N=511000,M=4110000;
struct edge{int x,y,pre;}a[M];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int id,dfn[N],low[N];
int root,cut[N];
int top,sta[N];
int cnt;
vector<int>vdcc[N];
void tarjan(int x){
dfn[x]=low[x]=++id;
sta[++top]=x;
int child=0;
if(x==root&&last[x]==0){
vdcc[++cnt].push_back(x);
return;
}
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(dfn[x]<=low[y]){
child++;
if(x!=root||child>1)cut[x]=1;
cnt++;
int z;
do{
z=sta[top--];
vdcc[cnt].push_back(z);
}while(z!=y);
vdcc[cnt].push_back(x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
alen=0;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
if(x==y)continue;
ins(x,y),ins(y,x);
}
for(int i=1;i<=n;i++){
if(!dfn[i])root=i,tarjan(i);
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++){
printf("%d ",vdcc[i].size());
for(int j=0;j<vdcc[i].size();j++){
printf("%d ",vdcc[i][j]);
}
puts("");
}
return 0;
}
v-DCC缩点
int nmu=cnt;//给每一个割点一个新的编号
for(int i=1;i<=n;i++){
if(cut[i])new[i]=++num;
}
for(int i=1;i<=cnt;i++){//每一个v-DCC与它包含的割点连边
for(int j=0;j<vdcc[i].size();j++){
int x=vdcc[i][j];
if(cut[x]){
add(i,new[x]);
add(new[x],i);
}
else c[x]=i;
}
}
强连通分量（SCC）
给定一张有向图，若对于图中任意两个节点 \(x,y\)，既存在从 \(x\) 到 \(y\) 的路径，也存在从 \(y\) 到 \(x\) 的路径，则称该有向图是“强连通图”。
有向图的极大强连通子图被称为“强连通分量”，简记为"\(SCC\)"。
强连通分量判定法则
在追溯值的计算过程中，若从 \(x\) 回溯前，有 \(dfn[x]=low[x]\)，则栈中从 \(x\) 到栈顶的所有节点构成一个强连通分量。
#include<bits/stdc++.h>
using namespace std;
const int N=11100,M=111000;
struct edge{int x,y,pre;}a[M];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=edge{x,y,last[x]};last[x]=alen;}
int id,dfn[N],low[N],v[N],c[N];
int top,sta[N];
int cnt;
vector<int>scc[N];
void tarjan(int x){
dfn[x]=low[x]=++id;
sta[++top]=x;
v[x]=1;
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(v[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
cnt++;
int y;
do{
y=sta[top--];
v[y]=0;
c[y]=cnt;
scc[cnt].push_back(y);
}while(y!=x);
}
}
int main(){
int n,m;scanf("%d%d",&n,&m);
alen=0;memset(last,0,sizeof(last));
for(int i=1;i<=m;i++){
int x,y;scanf("%d%d",&x,&y);
ins(x,y);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=cnt;i++){
sort(scc[i].begin(),scc[i].end());
}
memset(v,0,sizeof(v));
printf("%d\n",cnt);
for(int i=1;i<=n;i++){
if(v[c[i]])continue;
v[c[i]]=1;
for(int j=0;j<scc[c[i]].size();j++){
printf("%d ",scc[c[i]][j]);
}
puts("");
}
return 0;
}
SCC缩点
for(int x=1;x<=n;x++){
for(int k=last[x];k;k=a[k].pre){
int y=a[k].y;
if(c[x]==c[y])continue;
add(c[x],c[y]);
}
}