一、概念

概念：

1.桥： 如果在图G中删去一条边e后，图G的连通分支数增加，即W(G-e)>W(G)，则称边u为G的桥，又称割边或关节边。

2.割点：如果在图G中删去一个结点u后，图G的连通分枝数增加，即W(G-u)>W(G)，则称结点u为G的割点，又称关节点。

3.点双连通分量：不含割点的连通子图

4.边双连通分量：不含割边的连通子图

性质：

1.边双连通分量中，任意两点都在某个边环中。（任意两点不一定在点环中）

2.点双连通分量中，任意两点都在某个点环中。

3.点双连通分量不一定是边双连通分量，边双连通分量不一定是点双连通分量。

二、求桥模板

#define N 100100#define M 200110#define INF 0x3fffffffstruct node{    int from,to,next;}edge[2*M];vector
     
      mat[N];//用来建新图.int n,m;int savex[M],savey[M];int cnt,pre[N];bool mark[2*M];bool save[2*M];int low[N];int mylink[N];void add_edge(int u,int v){    edge[cnt].to=v;    edge[cnt].from=u;    edge[cnt].next=pre[u];    pre[u]=cnt++;}void dfs(int s,int num)//寻找桥{    low[s] = num;    int mi=num;    for(int p=pre[s];p!=-1;p=edge[p].next)    {        int v=edge[p].to;        if(mark[p]==1) continue;        if(low[v]==-1)        {            mark[p]=1;            mark[p^1]=1;            dfs(v,num+1);            if(low[v]>num) // 说明edge[p]是桥            {                save[p]=1;                save[p^1]=1;            }        }        mi=min(mi,low[v]);    }    low[s]=mi;}void dfs1(int s,int num)//缩点{    mylink[s]=num;    mark[s]=1;    for(int p=pre[s];p!=-1;p=edge[p].next)    {        int v=edge[p].to;        if(mark[v]==1||save[p]==1) continue;        dfs1(v,num);    }}void init(){    cnt=0;    memset(pre,-1,sizeof(pre));}int main(){    init();    //构图    scanf("%d%d",&n,&m);    for(int i=0;i
     

找到桥后，除去桥后的图中连通块即为边双连通分量。

 

三、割点模板

#define N 110#define M N*Nstruct node{    int to,next;}edge[2*M];int n;//图中节点个数，边的个数int pre[N],cnt;bool cutmark[N];int vis[N];int indx;int mylink[N];int tn;void init(){    memset(pre,-1,sizeof(pre));    cnt = 0;}void add_edge(int u,int v)//向图中插入一条无向边{    edge[cnt].to = v;    edge[cnt].next = pre[u];    pre[u] = cnt++;    edge[cnt].to = u;    edge[cnt].next = pre[v];    pre[v] = cnt++;}void build_map()//构图{    init();    //然后就是加边//    char str[10010];//    getchar();//    while(gets(str) && str[0]!='0')//    {//        stringstream in(str);//        int tmp;//        int tu=0;//        int flag=0;//        while(in>>tmp)//        {//            if(flag == 0)//            {//                flag = 1;//                tu = tmp;//            }//            else//            {//                add_edge(tu,tmp);//            }//        }//    }    }void dfs(int s,int fa,bool sign)//寻找割点{    vis[s] = ++indx;    int _mi = indx;//这个结点所能到达的最上层    int _cutedge = 0;    for (int p=pre[s]; p!=-1; p=edge[p].next) {        int _v = edge[p].to;        if(_v == fa) continue;        if(vis[_v] == -1)        {            dfs(_v,s,sign|1);            if(vis[_v] >= vis[s])            {                _cutedge ++;            }        }        _mi = min(_mi,vis[_v]);    }    vis[s] = _mi;    if( (sign == 0&&_cutedge>1)||(sign == 1&&_cutedge>0) )    {        cutmark[s] = 1;//为割点    }}void find_cutnode(){    memset(cutmark,0,sizeof(cutmark));    memset(vis,-1,sizeof(vis));    indx = 0;    for(int i=1;i<=n;i++)    {        if(vis[i] == -1)        {            dfs(i,-1,0);        }    }    //是否为割点，存在cutmark中}void dfs1(int s,int _id)//缩点用DFS{    mylink[s] = _id;    for(int p=pre[s];p!=-1;p=edge[p].next)    {        int _v = edge[p].to;        if(mylink[_v] == 0 && cutmark[_v] == 0)        {            dfs1(_v,_id);        }    }}void shuodian()//缩点,对应为[1-tn]中的点{    tn = 0;    memset(mylink,0,sizeof(mylink));    for(int i=1;i<=n;i++)    {        if(mylink[i] == 0 && cutmark[i] == 0)        {            dfs1(i,++tn);        }    }    //然后把割点也算成一个点双连通块    for(int i=1;i<=n;i++)    {        if(cutmark[i] == 1)        {            mylink[i] = ++tn;        }    }    //tn 表示点双连通块的个数.}

同理，除去割点后，剩余图中的连通块即为点双连通分量。