1.割点、割边都是在深度优先生成树的基础上判断割点： $low[v]>=num[u]\&\&u!=1$ 或者顶点（将1设为顶点）有两个或两个以上孩子判断割边： $low[v]>num[u]\&\&u!=1$ 或者顶点（将1设为顶点）的孩子v有个兄弟以下代码将 $low[v]>=num[u]\&\&u!=1$ 改为 $low[v]>num[u]\&\&u!=1$ 就是求割边的数量

poj 1144

题意: 给定一组点集以及边集，并且保证组成的图一定是联通的。求关键点的数量，任意删去一个关键点点以及其所连接的边，都会造成图的不连通每组例子，先输入一个n，代表点的个数；然后输入一个数，该行都与这个数存在边，一直到一行的第一个数都为0时，这个图就结束了。

#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=107;
int low[maxn],num[maxn],dfn,ans;
bool iscut[maxn];
vector<int>g[maxn];
void dfs(int u,int fa) {
    low[u]=num[u]=++dfn;
    int son=0;
    for(int i=0;i<g[u].size();++i) {
        int v=g[u][i];
        if(v==fa) continue;
        if(!num[v]) {
            ++son;
            dfs(v,u);
            low[u]=min(low[v],low[u]);
            if(low[v]>=num[u]&&u!=1) iscut[u]=true;
        }
        //else if(num[v]<num[u]) low[u]=min(low[u],num[v]);
        else if(low[u]>num[v]) low[u]=num[v];
    }
    if(u==1&&son>=2) iscut[1]=true;
    ans+=iscut[u];
}
int main() {
    int n;
    while(cin>>n&&n) {
        memset(num,0,sizeof num);
        memset(iscut,false,sizeof iscut);
        for(int i=0;i<=n;++i) g[i].clear();
        int u,v;
        while(cin>>u&&u) {
            while(getchar()!='\n') {
                cin>>v;
                g[u].push_back(v),g[v].push_back(u);
            }
        }
        ans=dfn=0;
        dfs(1,-1);
        cout<<ans<<endl;
    }
}

2.双连通分量之点双连通分量

poj 1523

题意：求割点并输出删去割点后能将图分成几部分输入的边可能有好多条，一定要用向前星存图。

#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1005;
int low[maxn],num[maxn],dfn;
bool iscut[maxn],vis[maxn];
int head[maxn],Next[maxn*maxn],to[maxn*maxn],tot;
void add(int x,int y) {
	to[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
}
void dfs(int u,int fa) {
    low[u]=num[u]=++dfn;
    int son=0;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==fa) continue;
        if(!num[v]) {
            ++son;
            dfs(v,u);
            low[u]=min(low[v],low[u]);
            if(low[v]>=num[u]&&u!=1) iscut[u]=true;
        }
        else if(low[u]>num[v]) low[u]=num[v];
    }
    if(u==1&&son>=2) iscut[1]=true;
}
void find(int u) {
	vis[u]=true;
	for(int i=head[u];i;i=Next[i]) {
		int v=to[i];
		if(!vis[v])
			find(v);
	}
}
int main() {
    int u,v,n,cas=0;
    while(scanf("%d",&u)&&u) {
        memset(num,0,sizeof num);
        memset(iscut,false,sizeof iscut);
        memset(head,0,sizeof head);
        tot=0;
        scanf("%d",&v);
        if(u>v) n=u;
		else n=v;
        add(u,v),add(v,u);
        while(scanf("%d",&u)&&u) {
        	if(n<u) n=u;
        	scanf("%d",&v);
        	if(n<v) n=v;
        	add(u,v),add(v,u);
        }
        dfn=0;
        dfs(1,-1);
        printf("Network #%d\n",++cas);
        bool flag=false;
        for(int i=1,son;i<=n;++i) {
        	if(!iscut[i]) continue;
        	flag=true;	son=0;
        	memset(vis,false,sizeof vis);
        	vis[i]=true;
        	for(int j=head[i],v;j;j=Next[j]) {
        		v=to[j];
        		//cout<<v<<" "<<vis[v]<<endl;
        		if(!vis[v]) {
        			find(v);
        			++son;
				}
			}
			printf("  SPF node %d leaves %d subnets\n",i,son);
		}
		if(!flag) printf("  No SPF nodes\n");
		printf("\n");
    }
    return 0;
}

3.双连通分量之边双连通分量将图G中的所有边双连通分量缩成一个点--“缩点技术”。这些点构成缩点树，加多少条边使G双连通，转化成加多少条边使得缩点树变成一个边双连通图。知识增加的边数=（总度数为1的结点数+1）/2 这个代码里low[]值相同的确实是一个边双连通图，但是不同的不一定不是边双连通图，比如： 7 8 2 5 2 3 5 1 5 6 3 1 3 6 3 4 3 7 这组数据选择1为顶点和选择2为顶点求得的l边双连通图的数量不一样多。

poj 3352

给定一个无向图G，图中没有重边。问添加几条便才能使无向图变成边双连通图。

#include<cstring>
#include<vector>
#include<stdio.h>
using namespace std;
const int maxn=1005;
int n,m,low[maxn],dfn;
vector<int>g[maxn];
void dfs(int u,int fa) {
 	low[u]=++dfn;
 	for(int i=0;i<g[u].size();++i) {
 		int v=g[u][i];
 		if(v==fa) continue;
 		if(!low[v])
 			dfs(v,u);
 		low[u]=min(low[u],low[v]);
	}
}
int tarjan() {
 	int degree[maxn];
 	memset(degree,0,sizeof degree);
 	for(int i=1;i<=n;++i)
 	for(int j=0;j<g[i].size();++j) if(low[i]!=low[g[i][j]])
 		++degree[low[i]];
 	int ans=0;
 	for(int i=1;i<=n;++i) if(degree[i]==1)
 		++ans;
 	return ans;
}
int main() {
	while(~scanf("%d%d",&n,&m)) {
		memset(low,0,sizeof low);
		for(int i=0;i<=n;++i) g[i].clear();
		for(int i=1;i<=m;++i) {
			int a,b;
			scanf("%d%d",&a,&b);
			g[a].push_back(b),g[b].push_back(a);
		}
		dfn=0;
		dfs(1,-1);
		printf("%d\n",(tarjan()+1)/2);
	}
}

无向图的连通性

poj 1144

poj 1523

poj 3352