点双连通分量是指在无向图中，由极大点双连通的子图组成的一种特殊结构。割点是指对于一个连通图中的点 x,如果删去这个点以及与所有 x 相连的边之后图不连通，那么称 x 为该图的割点。点双联通是指对于一个无向图，如果该图中不存在割点，那么称这个图是点双联通的。
下面是一个简单的证明：
设 G(V,E) 是无向图，则 G 的邻接矩阵 A 为 $n \times n$ 的矩阵，其中 $A[i][j]$ 表示节点 i 和节点 j 之间是否存在一条边。设 D(V) 是 D(V) 的一个子集，且 D(D) 是 D(D) 的一个子集。若 G 为双连通图，则对于任意两个不同的顶点 i、j,都有至少一条路径 p=(i1,i2...ik-1,ij...jk-1,j),使得 p∩ D=D' 或 p∩ D=φ。因此 D' 是双连通子图。
为了方便起见，我们将上述结论简化为以下三个性质：
1. 任意两点间都存在至少两条非重复路径；
2. 图中任意一个割点都在至少两个点双中；
3. 任意一个不是割点的点都只存在于一个点双中。
设 dfn[x] 表示遍历到 x 之前遍历过多少个点，low[x] 表示从 x 出发在不经过父子边的情况下能到达的最早的祖先的 dfn 值。
回看割点的定义：把这个点删除后图会不连通，那么肯定存在一些点，在不经过该割点的情况下无法到达割点的祖先，用这个性质来找就好了。
代码如下：
重构后的代码如下：
```cpp
int dfn[maxn], low[maxn], id;
bool cut[maxn];
void dfs1(int x, int from) {
dfn[x] = low[x] = ++id;
int son = 0;
for (int i = first[x]; i; i = e[i].next) {
int y = e[i].y;
if (y == (from ^ 1)) continue; // 不能通过反向边走回去
if (!dfn[y]) {
dfs1(y, x);
son++;
if (low[y] < low[x]) low[x] = low[y]; // 更新low,假如y能走到更小的，那么x也能走到
if (low[y] >= dfn[x]) cut[x] = true; // 假如儿子在不经过父子边的情况下不能到达x的祖先，那么x就是个点
} else if (dfn[y] < low[x]) low[x] = dfn[y]; // 假如走到了一个dfn更小的，那么更新low
}
if (fa == -1 && son == 1) cut[x] = false; // 特判出发点在一个环中的情况
}
void tarjan() {
for (int i = 1; i <= n; i++) // 如果图不连通，那么每一个连通块都要跑一遍
if (dfn[i] == 0) dfs1(i, -1);
}
```
特判是用来处理从红色节点出发的情况。如果从红色节点出发，最后红色节点会被判定成割点，因为没有儿子能走到它的祖先。但是它压根就没有祖先，所以这时候，我们判断一下，假如没有祖先，那么不能算割点，于是有了 `fa == -1` 这个判定条件。而 `son == 1` 这个条件用来判断出发点是否在环中。如果出发点在环中，那么它也可能是割点。
这个限制了，因为如果起点是割点，那么son肯定大于1。
在这个问题中，我们需要重构以下内容：
```
发现只有遍历到一个dfn[y]=0的y时，son才会+1,所以son的实际意义就是该点所连接的点双数量。
```
重构后的内容如下：
当遍历到`dfn[y] = 0`且`y`满足条件时，我们认为`son`的数量会增加1。因此，可以得出结论：`son`的实际意义是表示与该点相连的点的对数。
代码示例(Python):
```python
if dfn[y] == 0:
son += 1
```
根据上述性质，我们可以得出以下结论：
1. 如果$s\oplus n=1$,那么这个点肯定不是割点。
2. 如果$s\oplus n=1$,并且$son=1$,那么这个点一定是割点。
3. 如果$fa=-1$,那么这个点一定不是割点。
4. 如果$fa=-1$,并且$son=1$,那么这个点一定是割点。
在第4种情况下，我们需要进行$son=1$的判断。这是因为在割点的定义中，对于任意一条有向边$(u,v)$,如果存在一个顶点$w$,使得$uw\neq uv$,那么$w$就是割点。而在这个例子中，由于$fa=-1$,所以存在一个顶点$w$,使得$uw\neq uv$。因此，根据第4种情况，我们可以得出结论：在给定的图中，存在一个割点。
那可能有人会问了，为什么其他的割点不用如下的方法来判断呢？仔细想想，其他的点和出发点的区别就是：他们都有父亲。而遍历的时候是不能往回走的，也就是说，我们不知道父亲的状态，所以不能用如下的方法来判断。
找点双
这个时候就要请出伟大的 Tarjan 了！我们依然考虑使用上面的深度优先搜索(DFS)和广度优先搜索(BFS)来求，我们将深搜时遇到的所有边加入到栈里面，当找到一个割点的时候，就将这个割点往下走到的所有边弹出，而这些边所连接的点就是一个点双了。
代码：
以下是重构后的内容：
```cpp
int dfn[maxn], low[maxn], id, t;
edge zhan[(maxn * maxn) << 1]; //存边的栈
int belong[maxn], cnt; //belong记录每个点属于哪一个点双，cnt记录点双个数
bool cut[maxn];
set<int> s[maxn]; //记录每个点双包含哪些点，如果题目不需要也可以不求
void dfs(int x, int from) {
dfn[x] = low[x] = ++id;
int son = 0;
for (int i = first[x]; i; i = e[i].next) {
if (i == (from ^ 1)) continue;
int y = e[i].y;
if (!dfn[y]) {
zhan[++t] = e[i];
dfs(y, i);
son++; //先压栈再遍历
if (low[y] < low[x]) low[x] = low[y];
if (low[y] >= dfn[x]) //发现x是割点
{
cnt++;
edge xx;
cut[x] = true;
do {
xx = zhan[t--]; //弹出
belong[xx.x] = belong[xx.y] = cnt; //标记
s[cnt].insert(xx.x); s[cnt].insert(xx.y); //记录
} while (xx.x != x || xx.y != y); //假如已经弹到 x到y 这条边了，就停下来
}
} else if (dfn[y] < low[x]) low[x] = dfn[y];
}
if (from == -1 && son == 1) cut[x] = false;
}
```
请根据提供的内容完成内容重构，并保持段落结构：
边不重复的路径。找割边和找割点类似，直接上代码：
```cpp
int dfn[maxn], low[maxn], id;
bool cut[maxn];
void dfs(int x, int from) {
dfn[x] = low[x] = ++id;
for (int i = first[x]; i; i = e[i].next) {
int y = e[i].y;
if (!dfn[y]) {
dfs(y, i);
if (low[y] < low[x]) low[x] = low[y];
if (low[y] > dfn[x]) cut[i] = cut[i ^ 1] = true;
// 注意这里是大于而不是大于等于，原因想想就明白了
} else if (dfn[y] < low[x]) low[x] = dfn[y];
}
}
```
找边双的做法：
做法1:在请出Tarjan之前，我们先介绍另外一种做法：第一次找出割边，然后第二次找出割边。在不经过割边的情况下遍历所有点，每一次遍历经过的一个子图就是一个边双。
做法2:用类似找点双的做法，但是栈里面压点，不压边。代码如下：
以下是重构后的代码：
```cpp
int dfn[maxn], low[maxn], belong[maxn];
int id = 0, cnt = 0;
int zhan[maxn], t = 0;
void dfs(int x, int from) {
dfn[x] = low[x] = ++id;
zhan[++t] = x;
for (int i = first[x]; i; i = e[i].next) {
if (i == (from ^ 1)) continue;
int y = e[i].y;
if (!dfn[y]) {
dfs(y, i);
if (low[y] < low[x]) low[x] = low[y];
} else if (dfn[y] < low[x]) low[x] = dfn[y];
}
if (dfn[x] == low[x]) {
cnt++;
int xx;
do {
xx = zhan[t--];
belong[xx] = cnt;
} while (xx != x);
}
}
```
题表：Caocao's Bridges、Juice Junctions、Redundant Paths。
