Tarjan割边模板

#include<bits/stdc++.h>
#define N 1000020
using namespace std;

namespace zyt
{
	const int maxn=5e4 + 5;
	
	struct edges{
		int to,next; 
	}edge[600005];
	
	int cntx=0;
	int head[maxn];
	
	void add(int x,int y)
	{
		edge[cntx].to=y;
		edge[cntx].next=head[x];
		head[x] = cntx++;
	}
	
	int dfn[maxn],low[maxn];
	bool bridge[600005];
	int dcc[maxn],cnt=0,c=0;
	
	void tarjan(int x,int in_edge)
	{
		dfn[x]=low[x]=cnt++;
		for (int i=head[x]; i!=-1; i=edge[i].next)
		{
			int t=edge[i].to;
			if(!dfn[t])   
			{
				tarjan(t,i);
				low[x]=min(low[x],low[t]);    
				if(low[t]>dfn[x])
				{
					bridge[i]=bridge[i^1]=true;  
				} 
			}else if(i!=(in_edge^1))
				low[x]=min(low[x],dfn[t]); 	 
		}
	}
	
	void dfs(int x)
	{
		dcc[x] = c;
		for (int i=head[x];i!=-1; i=edge[i].next)
		{
			int y=edge[i].to;
			if(dcc[y]||bridge[i]) 
				continue;
			dfs(y); 
		}
	} 

	int work()
	{
		int n,m;
		cin>>n>>m;
		memset(head,-1,sizeof(head));
		for (int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			if(x==y) 
				continue; 
			add(x,y),add(y,x);
		} 
		for (int i=1;i<=n;i++)
		{
			if(!dfn[i]) tarjan(i,i);
		}
		for (int i=1;i<=n;i++)
		{
			if(!dcc[i])
			{
				c++;
				dfs(i);
			}
		}
		cout<<c<<endl;
		return 0;
	}
}
int main()
{
	return zyt::work();
}

代码讲解

代码总览

该程序使用了 Tarjan算法 来找出图中的所有桥（Bridge），然后通过DFS遍历标记每个节点所属的边双连通分量，最后输出分量的总数。

代码详解

1. 头文件与全局定义

#include<bits/stdc++.h>
#define N 1000020
using namespace std;

• #include<bits/stdc++.h>：包含所有标准库头文件，常见于竞赛编程中，但不推荐在生产环境中使用。
• #define N 1000020：定义常量N，表示最大节点数（但实际代码中使用了maxn=5e4+5，所以这里可能未使用）。
• using namespace std;：使用标准命名空间。

2. 命名空间 zyt

将主要逻辑封装在命名空间zyt中，避免全局变量污染。

3. 图的结构定义

struct edges{
    int to,next; 
}edge[600005];

• 使用链式前向星存储图结构。
  • to：边的终点。
  • next：指向下一条边的索引。

4. 全局变量

int cntx=0;         // 边计数器
int head[maxn];     // 头指针数组
int dfn[maxn];      // DFS序（时间戳）
int low[maxn];      // 当前节点能够回溯到的最早访问的节点的时间戳
bool bridge[600005];// 标记某条边是否为桥
int dcc[maxn];      // 记录每个节点所属的边双连通分量编号
int cnt=0;          // 时间戳计数器
int c=0;            // 边双连通分量计数器

• cntx：用于记录边的数量，每次加边时递增。
• head：存储每个节点的第一条边。
• dfn：记录每个节点在DFS遍历中的顺序（时间戳）。
• low：记录当前节点通过其子孙节点能回溯到的最小时间戳。
• bridge：标记某条边是否为桥（即删除后图不再连通）。
• dcc：记录每个节点属于哪个边双连通分量。
• cnt：DFS时间戳。
• c：边双连通分量的数量。

5. 加边函数

void add(int x,int y) {
    edge[cntx].to=y;
    edge[cntx].next=head[x];
    head[x] = cntx++;
}

• 标准的链式前向星加边操作，注意这里添加的是无向边，所以每条边会添加两次（正向和反向）。

6. Tarjan算法找桥

void tarjan(int x,int in_edge) {
    dfn[x]=low[x]=cnt++;
    for (int i=head[x]; i!=-1; i=edge[i].next) {
        int t=edge[i].to;
        if(!dfn[t]) {
            tarjan(t,i);
            low[x]=min(low[x],low[t]);
            if(low[t]>dfn[x]) {
                bridge[i]=bridge[i^1]=true;
            }
        } else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[t]);
    }
}

• in_edge：记录进入当前节点的边（防止重复访问父节点）。
• dfn[x] = low[x] = cnt++：初始化当前节点的时间戳。
• 遍历所有邻接节点：
  • 如果未访问过（!dfn[t]），则递归调用tarjan，并更新low[x]。
  • 如果满足low[t] > dfn[x]，说明边(x, t)是桥（因为t无法通过其他路径回到x或更早的节点），标记该边及其反向边为桥。
  • 如果邻接节点已访问过且不是当前边的反向边（防止直接回溯），则用其dfn更新low[x]。

7. DFS标记边双连通分量

void dfs(int x) {
    dcc[x] = c;
    for (int i=head[x];i!=-1; i=edge[i].next) {
        int y=edge[i].to;
        if(dcc[y]||bridge[i]) 
            continue;
        dfs(y); 
    }
} 

• 遍历所有节点，如果节点还未被标记分量（!dcc[y]）且边不是桥，则继续DFS。
• 注意：桥不属于任何边双连通分量，所以遇到桥就跳过。

8. 主逻辑函数 work()

int work() {
    int n,m;
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for (int i=1;i<=m;i++) {
        int x,y;
        cin>>x>>y;
        if(x==y) continue; 
        add(x,y),add(y,x);
    } 
    for (int i=1;i<=n;i++) {
        if(!dfn[i]) tarjan(i,i);
    }
    for (int i=1;i<=n;i++) {
        if(!dcc[i]) {
            c++;
            dfs(i);
        }
    }
    cout<<c<<endl;
    return 0;
}

• 读入节点数n和边数m。
• 初始化head为-1（链式前向星空表标志）。
• 读入边，忽略自环（x==y）。
• 对每个未访问的节点调用tarjan找桥。
• 再次遍历所有节点，如果未标记分量，则进行DFS标记该连通分量中的所有节点（跳过桥）。
• 输出边双连通分量的数量c。

9. main函数

int main() {
    return zyt::work();
}

• 直接调用zyt::work()并返回结果。

算法学习推荐

1. 链式前向星

• 介绍：一种高效的图的存储方式，尤其适用于稀疏图。
• 推荐学习网址：
  • 链式前向星 - OI Wiki

2. Tarjan算法

• 介绍：用于求解图的强连通分量（有向图）、桥和割点（无向图）。
• 推荐学习网址：
  • Tarjan算法 - OI Wiki
  • 桥与割点 - OI Wiki
  • YouTube视频讲解（英文）

3. 边双连通分量（e-DCC）

• 介绍：删除图中所有桥后，剩余的连通块即为边双连通分量。
• 推荐学习网址：
  • 双连通分量 - OI Wiki
  • CF博客：边双连通分量

总结

该代码通过以下步骤求解边双连通分量：

1. 使用链式前向星存储图。
2. 应用Tarjan算法标记所有桥。
3. 通过DFS（跳过桥）标记每个节点所属的边双连通分量。
4. 统计分量的数量并输出。

注意：边双连通分量中不包含桥，且每个节点属于且仅属于一个边双连通分量。

作业第二题代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct graph{
    int head[maxn],nxt[maxn],to[maxn],flag[maxn],cnt;
    inline graph():cnt(1){}
    inline void add(int u,int v,int w){
        nxt[++cnt]=head[u];
        to[cnt]=v;
        head[u]=cnt;
        flag[cnt]=w;
    }
}gr,cgr;
int n,m,dfn[maxn],low[maxn],st[maxn],color[maxn],idx,col,top,a,b;
int f[maxn];
void tarjan(int u,int fa){
    dfn[u]=low[u]=++idx;
    st[++top]=u;
    for(int i=gr.head[u];i;i=gr.nxt[i]){
        int v=gr.to[i];
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }else if(!color[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        col++;
        while(st[top]!=u){
            color[st[top]]=col;
            top--;
        }
        color[u]=col;
        top--;
    }
}
void dfs(int u,int fa){
    for(int i=cgr.head[u];i;i=cgr.nxt[i]){
        int v=cgr.to[i],w=cgr.flag[i];
        if(v==fa)continue;
        f[v]|=f[u]|w;
        dfs(v,u);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        gr.add(u,v,w);
        gr.add(v,u,w);
    }
    cin>>a>>b;
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,0);
    }
    int tot=0;
    for(int u=1;u<=n;u++){
        for(int i=gr.head[u];i;i=gr.nxt[i]){
            tot++;
            int v=gr.to[i],w=gr.flag[i];
            if(color[u]==color[v]){
                f[color[u]]|=w;
            }else{
                //注意这里存图的边数要乘4倍
                cgr.add(color[u],color[v],w);
                cgr.add(color[v],color[u],w);
            }
        }
    }
    dfs(color[a],0);
    if(f[color[b]]){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

代码解释与算法学习推荐

代码功能概述

这段代码解决的是无向图中两点间路径存在问题：给定一个无向图，每条边有一个权重（0或1），判断从节点a到节点b是否存在至少一条路径，该路径上至少有一条边的权重为1。

代码结构分析

1. 图结构定义

struct graph{
    int head[maxn], nxt[maxn], to[maxn], flag[maxn], cnt;
    inline graph():cnt(1){}
    inline void add(int u, int v, int w){
        nxt[++cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt;
        flag[cnt] = w;
    }
} gr, cgr;

• 使用链式前向星存储图结构
• gr存储原图，cgr存储缩点后的图
• flag数组存储边的权重（0或1）

2. Tarjan算法实现

void tarjan(int u, int fa){
    dfn[u] = low[u] = ++idx;
    st[++top] = u;
    for(int i = gr.head[u]; i; i = gr.nxt[i]){
        int v = gr.to[i];
        if(v == fa) continue;
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        } else if(!color[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        col++;
        while(st[top] != u){
            color[st[top]] = col;
            top--;
        }
        color[u] = col;
        top--;
    }
}

• 用于寻找无向图的边双连通分量
• dfn记录访问时间戳，low记录能回溯到的最早节点
• 通过栈管理节点，发现强连通分量时出栈并染色

3. DFS遍历

void dfs(int u, int fa){
    for(int i = cgr.head[u]; i; i = cgr.nxt[i]){
        int v = cgr.to[i], w = cgr.flag[i];
        if(v == fa) continue;
        f[v] |= f[u] | w;
        dfs(v, u);
    }
}

• 在缩点后的图上进行深度优先搜索
• 传播标记信息f，记录从起点到当前节点的路径上是否有权重为1的边

4. 主函数流程

1. 读入节点数n和边数m
2. 构建原图
3. 读入起点a和终点b
4. 使用Tarjan算法进行边双连通分量缩点
5. 构建缩点后的图：
   • 同一分量内的边权重进行"或"操作
   • 不同分量间保留边及其权重
6. 从起点所在分量开始DFS
7. 检查终点所在分量的标记情况

算法学习推荐

1. Tarjan算法

• 用途：寻找有向图或无向图的强连通分量/边双连通分量
• 学习资源：
  • Tarjan算法详解 - OI Wiki
  • 强连通分量 - 维基百科
  • Tarjan's Algorithm - GeeksforGeeks

2. 图论基础

• 学习资源：
  • 图论基础 - OI Wiki
  • 图论算法入门 - CP-Algorithms
  • 图论教程 - TutorialsPoint

3. 深度优先搜索(DFS)

• 学习资源：
  • 深度优先搜索 - OI Wiki
  • DFS算法详解 - GeeksforGeeks

4. 竞赛编程平台

• 实践平台：
  • LeetCode
  • Codeforces
  • AtCoder
  • 洛谷

代码优化建议

1. 数组大小：当前maxn=1e6+5可能不足以处理大规模数据，应根据题目要求调整
2. 内存管理：考虑使用vector代替静态数组，提高灵活性
3. 算法效率：Tarjan算法的时间复杂度为O(V+E)，适合大规模图处理
4. 代码可读性：添加更多注释，特别是算法关键步骤的说明

这段代码展示了图论中常见的缩点技术，通过将图简化为DAG（有向无环图），从而简化路径查询问题，是解决复杂图论问题的有效方法。