割点和割边
割点
定义：在一个连通分量中存在一些关键点，如果删除它，会把这个连通分量分成两个或多个，这种点称为割点。
在一个连通分量G中，对任意一点，做DFS，能够访问到所有点，产生一棵“深搜优先生成树”T。
定理1：T的根节点s是割点，当且仅当s有两个或两个以上的孩子节点。
定理2：T中非根节点u是割点，当且仅当u存在一个孩子节点v，v及其后代都没有回退边连回u的祖先。
编程实现定理2：
设u的一个直接后代是v
1) num[u], 记录DFS对每个节点的访问顺序。
2) low[v], 记录v和v的后代能够连回的祖先num。
3) 如果low[v] >= num[u], 说明v及v的后代都没有回退边回到u的祖先，那么u就是一个割点。
4) 搜完后还要对根节点特判是否是割点。
代码实现：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#define ll long long
const int mod = 1e9+7;
using namespace std;
vector<int>edge[1005];
int vis[1005],low[1005],num[1005],gd[1005],n,sum;
void dfs(int s,int f)
{
int cnt = 0;
sum++;
low[s] = num[s] = sum;//赋值，low的初值就是num
int l = edge[s].size();
for(int i = 0; i < l; i++){
int v = edge[s][i];
if(!num[v]){
cnt++;//当前节点的孩子个数
vis[v] = 1;
dfs(v,s);
low[s] = min(low[s],low[v]);//用后代更新low值。
if(low[v] >= num[s] && s != 1) gd[s] = 1;
}
else if(num[v] < num[s] && v != f) low[s] = min(low[s],num[v]);
//判断回退边，如果回退边的点的序号比s小，那么说明v是s的祖先，更新low[s].
}
if(s == 1 && cnt >= 2){
gd[s] = 1;//特判根节点
}
}
int main()
{
while(~scanf("%d",&n) && n){
sum = 0;
int t,u,v;
memset(vis,0,sizeof(vis));
memset(low,0,sizeof(low));
memset(gd,0,sizeof(gd));
memset(num,0,sizeof(num));
while(scanf("%d",&t) && t){
char c;
while(1){
scanf("%d%c",&v,&c);
edge[t].push_back(v);
edge[v].push_back(t);
if(c == '\n') break;
}
}
dfs(1,-1);
int ans = 0;
for(int i = 1; i <= n; i++){
if(gd[i]) ans++;
}
printf("%d\n",ans);
for(int i = 1; i <= n; i++) edge[i].clear();
}
return 0;
} 注意：如果想用vis判断某个点是否已经走过，那么vis要写在for循环外面，不能写在for的if判断里面。 巧妙的判断s和t之间的关键点方法：
从起点s到终点t的路径数等于经过点v的次数，那么点v就是连接s和v的关键点，如果删除这个点，那么s和t不能连通。很好理解，也就是说s到t的所有路径都要经过点v，没有点v这些路径都不能够连接到t点。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#define ll long long
const int mod = 1e9+7;
using namespace std;
vector<int>edge[2005];
int vis[1005],lz = 0,num[1005];
int n,m;
void dfs(int s,int t)
{
if(s == t){
lz++;
for(int i = 1; i <= n; i++){
if(vis[i]){
num[i]++;
}
}
return;
}
vis[s] = 1;
int l = edge[s].size();
for(int i = 0; i < l; i++){
int v = edge[s][i];
if(!vis[v]){
dfs(v,t);
}
}
vis[s] = 0;
}
int main()
{
int u,v;
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++){
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
scanf("%d%d",&u,&v);
dfs(u,v);
int cnt = 0;
for(int i = 1; i <= n; i++){
if(i != u && i != v){
if(num[i] == lz) cnt++;
}
}
if(cnt) printf("%d\n",cnt);
else printf("-1\n");
return 0;
} 割边
定义：在一个连通分量中删除一条边，把这个连通分量分成了两个，这个边称为割边。
改为：
if(low[v] > num[s] && s != 1)其他程序不变，可算出割边数量。
