浅谈无向图的割点和桥
无向图的割点和桥是用O(N)的速度求出一个无向图的割点与桥。代码不算很长
割点的含义：一个图中去掉一点及其向连的边，使得剩下的图被分为若干块
桥 的 含 义：一个图中去掉一边，使得剩下的图被分为若干块
误区：一个图中的割点与桥的数量关系不是固定的
A. 割点和割边
内存限制：64 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
给出一个无向连通图, 求出所有割点与割边的数量。
输入格式
第1行: 2个整数N，M (1 <= N <= 5,000，N-1 <= M <= 10,000)，分别表示顶点数和边数
接下来M行，每行2个整数，表示图中的一条边。
输出格式
第1行：1个整数，表示割点数
第2行：1个整数，表示割边数
样例输入
11 13
1 2
1 4
1 5
1 6
2 11
2 3
4 3
4 9
5 8
5 7
6 7
7 10
11 3
样例输出
11 13
1 2
1 4
1 5
1 6
2 11
2 3
4 3
4 9
5 8
5 7
6 7
7 10
11 3
我们用clk表示当前搜索到的节点的访问时间（全局变量）dfn表示当前节点搜索时的时间戳，low表示当前节点最早能回溯的节点的时间戳
（链式前向星储存边）
设当前点为u，考虑到如果u的子树不能连接到u的祖先(即low[v]>=dfn[u])，则该点为割点；如果u的子树不能连接到u及其祖先(即low[v]>dfn[u])，则该点为桥；
原因：一个是大于,一个是大于等于是因为假使其子树可以连通到点u，那么该子树到点u的边就至少两条（因为还有个u->v），所以该边就不是桥
不过这样做桥是搞定了，但是割点还是有些问题：
根节点的子树永远连不到根节点的祖先，所以怎么解决呢？
我们可以给根节点加一个特判：当该节点为根节点时，如果他的儿子只有一个，那么根节点就不是割点
不过我们又有个问题：如果子树能连到子树怎么办？
答案是不可能，假使如此，那么dfs便能一次捜完了。
AC代码
#include<cstdio>
#include<iostream>
#define inc(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
const int N=1e5+5;
int n,m,a1,a2,clk,p[N],dfn[N],low[N];
bool cut[N];
struct node{
int v,nt;
}E[2*N];
inline int read(){
int s=0,w=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
inline void insert(int u,int v){
E[++p[0]].v=v;
E[p[0]].nt=p[u];
p[u]=p[0];
}
inline void dfs(int u,int fa){
dfn[u]=low[u]=++clk;
int child=0;
for(int i=p[u];i;i=E[i].nt){
int v=E[i].v;
if(!dfn[v]){
child++;
dfs(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]) cut[u]=1;
if(low[v]>dfn[u]) a2++;
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
if(fa==-1&&child==1) cut[u]=0;
}
int main(){
n=read();m=read();
inc(i,1,m){
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
dfs(1,-1);
inc(i,1,n) if(cut[i]) a1++;
printf("%d\n%d",a1,a2);
return 0;
}