分量算法

1. tarjan算法详解--关于图的连通性 & 连通分量

Tarjan算法关于图的连通性和连通分量的详解如下：

有向图的强连通分量： 定义：在有向图中，如果存在一个子图，该子图中的任意两点间都存在双向可达路径，并且这个子图不能再扩大，则称这个子图为强连通分量。典型的例子是环。 时间戳和追溯值：在深度优先搜索过程中，为每个节点分配一个首次访问时间戳dfn，以及一个用于追踪子树中最早访问节点的low值。 计算方法：使用栈记录DFS路径，通过深度优先遍历更新low值。当发现某个节点的low值大于或等于其父节点的dfn值时，说明形成了一个强连通分量。

无向图的割点与桥： 割点：在无向图中，如果删除某个点后，图被分割成两个或更多个连通子图，则该点被称为割点。 桥：在无向图中，如果删除某条边后，图被分割成两个或更多个连通子图，则该边被称为桥。 判定桥：通过比较节点的dfn值和其子节点的low值来判断。如果边满足dfn[x] < low[y]，则说明没有其他路径可以从y到达x之前的节点，因此边是桥。

无向图的双连通分量： 点双连通分量：无割点的无向图中，极大且任意两点都在某个环中的连通子图。如果图中只有一个孤立点，它也构成一个点双连通分量。 边双连通分量：无桥的连通块，即每个连通块都是一个边双连通分量。

Tarjan算法通过深度优先搜索和栈等数据结构，高效地计算图的连通性和连通分量，对于理解图的结构和优化问题求解具有重要意义。