tarjan

1. 割点：删除该点后，图的连通分量数增加
2. 割边（桥）：删除该边后，图的连通分量数增加
3. 点双连通分量：无向图中极大的不含割点的连通子图
4. 边双连通分量：无向图中极大的不含割边的连通子图

---

• 割点
  • 根节点：如果有多于1个子树，则为割点
  • 非根节点u：存在子节点v，使得low[v]>=dfn[u]
• 割边
  • 对于边(u,v)，若low[v]>dfn[u]，则该边为割边
• 点双连通分量
  • 使用栈存储边
  • 当发现low[v]>=dfn[u]时，从栈中弹出边直到当前边，这些边属于同一个点双
• 边双连通分量
  • 先求出所有割边
  • 删除所有割边后，剩余的连通块就是边双连通分量
• 强连通分量

P3388 割点

void tarjan(int u, int fa) {
    int child = 0;
    dfn[u]=low[u]=++dfncnt;
    for (int i=frm[u];i;i=nxt[i]) {
        int v=to[i];
        if(!dfn[v]){
            child++;
            tarjan(v,u);
            low[u]=min(low[u], low[v]);
            if(low[v]>=dfn[u]&&fa!=u&&!vis[u]){
                cp++;
                vis[u]=true; // u为割点
            }
        }
        else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(child>1&&fa==u){
        if(!vis[u]){
            cp++;
            vis[u]=true;
        }
    }
}
int main() {
    for(int i=1;i<=n;i++)
        if(dfn[i]==0)
            tarjan(i,i);
    cout<<cp<<endl;
    for (int i=1;i<=n;i++)if(vis[i])cout<<i<<" ";
    return 0;
}

P8435 点双连通分量

int n,m;
int frm[N],to[M],nxt[M],_=1; // 从1开始，方便处理反向边
int dfn[N],low[N],dfncnt;
vector<int>dcc[N];
stack<int>stk;
int dcccnt,root;
void addedge(int u,int v){
    to[++_]=v;
    nxt[_]=frm[u];
    frm[u]=_;
}
void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    stk.push(u);
    if(u==root&&frm[u]==0){
        dcc[++dcccnt].push_back(u);
        return;
    }
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                dcccnt++;
                int w;
                do{
                    w=stk.top();stk.pop();
                    dcc[dcccnt].push_back(w);
                }while(w!=v);
                dcc[dcccnt].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v)continue; // 自环
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            root=i;
            tarjan(i);
        }
    }
    printf("%d\n",dcccnt);
    for(int i=1;i<=dcccnt;i++){
        printf("%d ",dcc[i].size());
        for(int j=0;j<dcc[i].size();j++)
            printf("%d ",dcc[i][j]);
        printf("\n");
    }
    return 0;
}

P8436 边双连通分量

#define N 500005
#define M 4000005
int n,m;
int frm[N],to[M],nxt[M],_=1;
int dfn[N],low[N],dfncnt;
int bridge[M],c[N],dcccnt;
vector<int>e[N]; // 存储每个边双的节点
void addedge(int u,int v){
    to[++_]=v;
    nxt[_]=frm[u];
    frm[u]=_;
}
void tarjan(int u,int in_edge){
    dfn[u]=low[u]=++dfncnt;
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])
                bridge[i]=bridge[i^1]=1;
        }
        else if(i!=(in_edge^1))
            low[u]=min(low[u],dfn[v]);
    }
}

void dfs(int u){
    c[u]=dcccnt;
    e[dcccnt].push_back(u);
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(c[v]||bridge[i])continue;
        dfs(v);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v)continue;
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i,0);
    for(int i=1;i<=n;i++)
        if(!c[i]){
            dcccnt++;
            dfs(i);
        }
    printf("%d\n",dcccnt);
    for(int i=1;i<=dcccnt;i++){
        printf("%d ",e[i].size());
        for(int j=0;j<e[i].size();j++)
            printf("%d ",e[i][j]);
        printf("\n");
    }
    return 0;
}

强连通分量

int dfn[N],low[N],dfncnt;
stack<int> stk;ins[N];               // 栈与在栈标记
int scc[N],scccnt;                   // scc[u]:u所属分量编号, sc:分量数
vector<int> comp[N];                 // 每个分量的节点
int printed[N];                      // 分量是否已输出

void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    stk.push(u);ins[u]=1;
    for(int i=frm[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ++scccnt;
        while(1){
            int x=stk.top();stk.pop();
            ins[x]=0;
            scc[x]=scccnt;
            if(x==u)break;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        addedge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++) comp[scc[i]].push_back(i);
    for(int i=1;i<=scccnt;i++) sort(comp[i].begin(),comp[i].end());

    cout<<scccnt<<"\n";
    int cnt=0;
    for(int i=1;i<=n;i++){
        int id=scc[i];
        if(!printed[id]){
            printed[id]=1; cnt++;
            for(int j=0;j<(int)comp[id].size();j++){
                if(j)cout<<" ";
                cout<<comp[id][j];
            }
            cout<<"\n";
            if(cnt==scccnt) break;
        }
    }
    return 0;
}