无向图：
(重)双连通分量 -- tarjan
区别：
桥： （一条无向边）
对于一个连通块，把一条无向边删除之后会出现不连通的情况，
那么这条无向边也就是-- 桥
包括：
1） 边双连通分量 e-DCC -- 极大的，不含有桥的连通块
性质： 1.任意删去一条边，整个图还是连通的
2.任意两点之间一定包含两条不想交的路径
在一个连通的无向图中，把一个点删去，整个图变得不连通--
这个点就是 -- 割点
2） 点双连通分量 v-DCC --极大的，不包含割点的连通块
没余个割点都至少属于两个连通分量
//极大的： 不存在任何一个包含他的且比他多的连通分量，那么他就是一个极大的连通分量
注意：
割点和桥之间没有本质关系
a.两个割点之间的 边不一定 是桥
b.桥的两个端点也不一定是割点
点连通分量 和边连通分量也没有本质关系
无向图的tarjan：
相比有向图，不存在横叉边，双向的--不存在往回走的情况，第一次dfs到就走过去了
1.判断桥(x<-->y)： dfn[x]<low[y] (y无论如何也走不到x)
2.如何找到边双连通分量：
func1： 将所有的桥删去--删完后剩下的每一个连通块都是一个边双连通分量
func2： 利用一个栈存每个连通块，当dfn[x]==low[x],栈中的节点也就是我们的连通块节点
连续题目：
题意： 给你一个无向连通图，问最少需要加几条边，使得图变成一个边双连通分量
应用结论： 对于图中任意两个点之间都包含至少2条相互分离的不同路径的话，
那么他就是一个双连通分量
思路：
缩点完后会变成一棵树
要想把得到的数变成一个边的双联通分量的话，
要把所有度数为1的点都加上一条边
结论：
1）有向图最少加几条边可以把它变成一个强连通分量--- max(p,q)//p--入度为0 的点， q --出度为0的点
2）无向图最少加几条边可以使他变成一个边的双联通分量 --(cnt+1)/2 , /--下取整 cnt --叶子节点(度数为1)个数
无向图tarjan代码：
/*
这里的tarjan算法求双联通分量和求强连通分量基本一样的
1.只不过无向图需要判断别走回路--反向边
2.还需要加一个桥的判断 -- dfn[u]<low[j], --j走不回u
*/
void tarjan(int u, int from) {
dfn[u] = low[u] = ++tim;
stk[++top] = u;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u]<low[j]) //这里j记录的 是点，i记录额是边
is_b[i] = is_b[i ^ 1] = true;
}
else if (i != (from ^ 1)) //i不是反向边
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
++dcc_cnt;
int y;
do {
y = stk[top--];
id[y] = dcc_cnt;
} while (y != u);
}
}步骤：
1.先用tarjan跑一遍来实现缩点，然后拿到一颗树
2.之后遍历所有边统计，边所在连通块的度
3.统计每个连通块的度，找出度为1的连通块数目--cnt
4.直接输出答案即可 ：（cnt+1)/2
电力：
题意 ：
给定一个由 n 个点 m 条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少
1.统计连通块个数 --cnt
2.依次枚举从哪个块中删那个点，看看可以分出几个块--s
最后得到连通块数量就是 s+cnt-1
//如何判断一个点是否是割点：x<-->y
low[y]>=dfn[x]
1)if x不是根节点 -- x一定是一个割点
2）x是根节点，则至少需要2个子节点 满足 low[y]>=dfn[x]
即在tarjan中加入一个割点判断：
void tarjan(int u) {
dfn[u] = low[u] = ++tim;
//当前块内，可以分出来的子树个数
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
if (low[j] >= dfn[u])++cnt;
}
else low[u] = min(low[u],dfn[j]);
}
// u不是根节点，并且已分出来了cnt课子树，再加一颗父亲
if (u != root && cnt) ++cnt;//此处说明这个点 是割点
ans = max(ans,cnt);
}说明如下：
3.AcWing 396. 矿场搭建（算法提高课） - AcWing
题意：
给定一个无向图，问最少在几个点上设置出口，
可以使得不管其他那个点坍塌，其余使用使用点都可以与某个出口连通
//条件：
1.出口数量 >=2
2.由于每个连通块里面的方案是相互独立，so 我们只需要
分别求出每个连通块，最后累积即可
1） 无割点（度数为0）：连通块内部有cnt个点 -- 可以任意选2个点
C(2,cnt) = cnt*（cnt-1）/2
2)有割点： 考虑缩点
//V-DCC的度数 ==1 ，需要在该连通块内部设置一个出口
//度数>1 ,无需设置出口
怎么求出点双连通分量呢 ？
利用栈存入 ，直到找到 x<--> y
利用 dfn[x]<=low[y] --判断出点x是割点
之后将栈中的元素弹出，直到弹出y为止，
且x也属于该点双连通分量
特判 -- 孤立点也是 双连通分量
怎么缩点:
1.每个割点单独作为一个点
2.从每个V-DCC向其所包含的每个割点连一条边
tarjan 代码：
void tarjan(int u) {
dfn[u] = low[u] = ++tim;
stk[++top] = u;
if (u == root && h[u] == -1) {
dcc_cnt++;
dcc[dcc_cnt].push_back(u);
return;
}
int cnt = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j]) {
cnt++;
if (u != root || cnt > 1)cut[u] = true;
++dcc_cnt;
int y;
do {
y = stk[top--];
dcc[dcc_cnt].push_back(y);
} while (y != j);
dcc[dcc_cnt].push_back(u);
}
}
else low[u] = min(low[u],dfn[j]);
}
}