tarjan

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

算法思路：

1. 割点：

   • 根节点：如果有多于1个子树，则为割点
   • 非根节点u：存在子节点v，使得low[v]>=dfn[u]

2. 割边：

   • 对于边(u,v)，若low[v]>dfn[u]，则该边为割边

3. 点双连通分量：

   • 使用栈存储边
   • 当发现low[v]>=dfn[u]时，从栈中弹出边直到当前边，这些边属于同一个点双

4. 边双连通分量：

   • 先求出所有割边
   • 删除所有割边后，剩余的连通块就是边双连通分量

P3388 割点

// dfn[u]: 节点u的DFS序号（时间戳）
// low[u]: 节点u或其子树能回溯到的最早的节点的DFS序号
// vis[u]: 标记节点u是否为割点，1表示是，0表示不是
// cp: 割点的计数器
// dfncnt: 全局时间戳计数器

// u: 当前正在访问的节点
// fa: 当前节点u在DFS树中的父节点
void tarjan(int u, int fa) {
    int child = 0; // 记录当前节点u在DFS树中的子节点数量
    dfn[u] = low[u] = ++dfncnt; // 初始化u的dfn和low值，并增加时间戳
    for (int i = frm[u]; i; i = nxt[i]) {
        int v = to[i];
        if (!dfn[v]) {
            child++; // 子节点数量加1
            tarjan(v, u);

            // 回溯后，用子节点v的low值更新u的low值
            // 这意味着u可以通过v到达更早的节点
            low[u] = min(low[u], low[v]);

            // --- 核心判断：割点条件 ---
            // 如果u不是根节点，并且存在一个子节点v，使得v的low值不小于u的dfn值
            // 这说明v及其子树无法通过其他路径回到u的祖先，因此u是割点
            // fa != u 确保了u不是根节点
            // !vis[u] 确保每个割点只被计数一次
            if (low[v] >= dfn[u] && fa != u && !vis[u]) {
                cp++; // 割点计数器加1
                vis[u] = true; // 标记u为割点
            }
        }
        // 情况2: v已经被访问过，且v不是u的父节点（即存在一条反向边）
        // 这条边可以用来更新u的low值，表示u可以通过这条反向边到达一个更早的节点v
        else if (v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    // --- 核心判断：根节点割点条件 ---
    // 如果u是DFS树的根节点（fa == u），并且它有两个或更多的子节点
    // 那么删除u后，这些子树将互不连通，所以u是割点
    if (child > 1 && fa == u) {
        // 注意：根节点可能在上面的if语句中已经被标记，所以这里需要判断
        if (!vis[u]) {
            cp++;
            vis[u] = true;
        }
    }
}
int main() {
    // 遍历所有顶点，确保处理非连通图的所有连通分量
    for(int i=1;i<=n;i++)
        if(dfn[i]==0) // 如果节点i未被访问过，说明它属于一个新的连通分量
            tarjan(i,i); // 从该节点开始DFS，并将其作为根节点
    cout<<cp<<endl;
    for (int i = 1; i <= n; i++)if(vis[i])cout<<i<<" ";
    return 0;
}

P8435 点双连通分量

#define N 500005
#define M 4000005
int n,m;
int frm[N],to[M],nxt[M],_=1; // 从1开始，方便处理反向边
int dfn[N],low[N],dfncnt;
vector<int>dcc[N]; // 存储每个点双的节点
stack<int>st;
int cnt,root;

void addedge(int u,int v){
    to[++_]=v;
    nxt[_]=frm[u];
    frm[u]=_;
}

void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    st.push(u);
    if(u==root&&frm[u]==0){ // 孤立点
        dcc[++cnt].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]){
                cnt++;
                int w;
                do{
                    w=st.top();st.pop();
                    dcc[cnt].push_back(w);
                }while(w!=v);
                dcc[cnt].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",cnt);
    for(int i=1;i<=cnt;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],dcc;
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]=dcc;
    e[dcc].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]){
            dcc++;
            dfs(i);
        }
    printf("%d\n",dcc);
    for(int i=1;i<=dcc;i++){
        printf("%d ",e[i].size());
        for(int j=0;j<e[i].size();j++)
            printf("%d ",e[i][j]);
        printf("\n");
    }
    return 0;
}

代码说明：

1. 点双连通分量：
   • 使用栈存储节点
   • 当发现割点条件时，从栈中弹出节点直到当前子节点
   • 注意根节点需要特殊处理
2. 边双连通分量：
   • 先求出所有桥
   • 删除桥后，剩下的连通块就是边双连通分量
   • 使用DFS标记每个节点所属的边双连通分量
3. 注意处理重边和自环的情况

缩点（找环）

• Tarjan-SCC：dfn/low+栈，dfn[u]==low[u] 时弹栈成一个强连通分量。
• 缩点建图：对每条原边(u,v)，若scc[u]!=scc[v]，连边 scc[u]→scc[v]，并统计入度。

#define N 1000005
#define M 4000005
int n,m;
int frm[N],to[M],nxt[M],_;          // 原图
int frm2[N],to2[M],nxt2[M],__;      // 缩点后的DAG
// dfn[u]:节点u的DFS序号（时间戳）
// low[u]:u或其子树能回溯到的最早的节点的DFS序号
// dfncnt:全局时间戳计数器
int dfn[N],low[N],dfncnt;
int st[N],top,ins[N];               // 栈与在栈标记
int scc[N],sc;                      // scc[u]:u所属强连通分量编号, sc:分量数
long long w[N],sumv[N],dp[N];       // w:点权, sumv:分量权值之和, dp: DAG上最长路
int indeg[N];                       // 缩点DAG入度

void addedge(int a,int b){          // 原图加边
    ++_; to[_]=b; nxt[_]=frm[a]; frm[a]=_;
}
void add2(int a,int b){             // 缩点DAG加边
    ++__; to2[__]=b; nxt2[__]=frm2[a]; frm2[a]=__;
}

void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    st[++top]=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]){
        ++sc;
        while(1){
            int x=st[top--];
            ins[x]=0;
            scc[x]=sc;
            sumv[sc]+=w[x];
            if(x==u)break;
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
    for(int i=1;i<=m;i++){
        int u,v; scanf("%d%d",&u,&v);
        addedge(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);

    for(int u=1;u<=n;u++){
        for(int i=frm[u];i;i=nxt[i]){
            int v=to[i];
            if(scc[u]!=scc[v]){
                add2(scc[u],scc[v]);
                indeg[scc[v]]++;
            }
        }
    }

    queue<int> q;
    for(int i=1;i<=sc;i++){
        dp[i]=sumv[i];
        if(!indeg[i]) q.push(i);
    }
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=frm2[u];i;i=nxt2[i]){
            int v=to2[i];
            if(dp[v]<dp[u]+sumv[v]) dp[v]=dp[u]+sumv[v];
            if(--indeg[v]==0) q.push(v);
        }
    }
    long long ans=0;
    for(int i=1;i<=sc;i++) ans=max(ans,dp[i]);
    printf("%lld\n",ans);
    return 0;
}

强连通分量

在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。

Tarjan-SCC：DFS维护 dfn/low 和一个栈，节点入栈并标记在栈中。

遍历边(u→v)：

若 v 未访问，递归后 low[u]=min(low[u],low[v])；

若 v 在栈内，low[u]=min(low[u],dfn[v])。

若 dfn[u]==low[u]，从栈中弹出直到 u，得到一个SCC。

输出：把每个点按所属SCC收集并排序；按点编号1…n扫描，遇到“第一次出现”的SCC就输出一行。

const int N=10005;
const int M=200005;

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

void tarjan(int u){
    dfn[u]=low[u]=++dfncnt;
    st[++top]=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]){
        ++sc;
        while(1){
            int x=st[top--];
            ins[x]=0;
            scc[x]=sc;
            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<=sc;i++) sort(comp[i].begin(),comp[i].end());

    cout<<sc<<"\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==sc) break;
        }
    }
    return 0;
}