点双/边双复习笔记
1.点双复习
割点：图中的一个点，没有这个点的话，这个图会变成两个图
点双：在一个点双内，一个点到另一个点的路径有两条及以上，并且点不会走一样的
注意事项：
1.割点特判：son<=1且fa = x的不是割点
2.环上出发特判:son=0&&fa=x的单独一个作为点双；
3.看好大于等于哦！
4.low[x]=min(low[to],low[x]);和low[x]=min(low[x],dfn[to]);注意区别（默写时这里出了问题）
算法思路：本质上是dfs，在dfs时记录一个点的最先遍历到的时间，成为dfn
维护这个点能到达的（除了不能走父亲连过来的那个边）最小dfn，成为low
利用性质找割点：要是一个节点的儿子dfs完了，但儿子的low是大于这个节点的dfn值，说明他的儿子只能经过父亲节点
回到优先遍历的点去，也就是说是割点，这时候弹栈直到这个儿子被弹出，这些弹出的和这个节点一起作为一个分量
然后这种dfs就叫tarjan(不会便利dfn已经有，也就是已经遍历过的节点）
注意下，老师说else low[x]=min(low[x],dfn[to]);要写else,否则的话可能会错。
重要代码
void tarjan(int x,int fa){
++t;
dfn[x]=t;
low[x]=t;
s[++top]=x;
int son=0;
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa){
continue;
}
if(!dfn[to]){
son++;
tarjan(to,x);
low[x]=min(low[to],low[x]);
if(low[to]>=dfn[x]){
cut[x]=1;
cnt++;
while(s[top+1]!=to){
bcc[cnt].push_back(s[top]);
top--;
}
bcc[cnt].push_back(x);
}
}
else low[x]=min(low[x],dfn[to]);
}
if(fa==x&&son==0){
bcc[++cnt].push_back(x);
}
if(fa==x&&son<=1){
cut[x]=0;
}
}
2.点双晚自习背诵默写及练习
https://www.luogu.com.cn/problem/P3225
评测情况：https://www.luogu.com.cn/record/115919126
这个是自己默写了一遍点双，然后wa的，原因是.low[x]=min(low[to],low[x]); 和 low[x]=min(low[x],dfn[to]);注意区别（默写时这里出了问题）
3.边双复习
割边：一个无向图，割去这条边，图就会分裂成多个图。
边双：不含这个割边的无向图。
写法差不多，和点双的区别在于
1.判定变为严格>而不是>=
2.栈的处理需要改变（出栈的结束点不同）
3.判断条件改变了，而且放在了一个点dfs完后
！！！！！4.！！！！！！！！重边的计算要考虑在内！！！！！！！！！
（模板没过），不然的话，我可能在fa==to那里错掉，因为
她不能从父亲dfs过来的那条便那里来，但是可以从另一条边来（重边）
但是，竟然是重边/自环，那么实质上这些重边性质都是相同的，都是链接u和v，然后我们又知道来的那条边有且只有一条
所以我在代码里加了f，把第一个来自父节点的边不遍历，后面全都继续做
AC了！！！！！
https://www.luogu.com.cn/record/115923273
代码：
void tarjan(int x,int fa){
++t;
dfn[x]=t;
low[x]=t;
top++;
s[top]=x;
bool f=0;//用来判重边,自环
for(int i=0;i<mp[x].size();i++){
int to=mp[x][i];
if(to==fa&&f==0){
f=1;
continue;
}
if(!dfn[to]){
tarjan(to,x);
low[x]=min(low[x],low[to]);
}
else low[x]=min(low[x],dfn[to]);
}
if(low[x]==dfn[x]){
cnt++;
while(s[top+1]!=x){
bcc[cnt].push_back(s[top]);
top--;
}
}
}
4.强连通分量：
其实强连通分量相比边双而言，就是在else low[x]=min(low[x],dfn[to]);这一句多了一句判断,要求to在栈里面才行
同时记得删去if(to==fa)continue这句，因为强连通分量时有向图