双连通分量（点-双连通分量&边-双连通分量）

概念：

双连通分量有点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。

一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。--百度百科

Tip：先学一下tarjan算法以及求割点割边的算法之后，再看会比较好理解一些。

点双连通和边双连通

连通的概念：在无向图中，所有点能互相到达
连通分量：互相联通的子图
点双连通：删掉一个点之后，图仍联通
边双连通：删掉一条边之后，图仍联通

概述

在一个无向图中，若任意两点间至少存在两条“点不重复”的路径，则说这个图是点双连通的（简称双连通,biconnected）

在一个无向图中，点双连通的极大子图称为点双连通分量（简称双连通分量,Biconnected Component,BCC）

性质

任意两点间至少存在两条点不重复的路径等价于图中删去任意一个点都不会改变图的连通性，即BCC中无割点
若BCC间有公共点，则公共点为原图的割点
无向连通图中割点一定属于至少两个BCC，非割点只属于一个BCC

算法

在Tarjan过程中维护一个栈，每次Tarjan到一个结点就将该结点入栈，回溯时若目标结点low值不小于当前结点dfn值就出栈直到目标结点（目标结点也出栈），将出栈结点和当前结点存入BCC

（说实话我觉得存点不比存边难理解和实现啊……下面会解释）

理解

首先申明一下，在我找到的BCC资料中，在算法实现中均将两个点和一条边构成的图称为BCC，此文章也沿用此的规定

如下图：

双连通分量（点-双连通分量&边-双连通分量）

我猜想可能是因为割点的定义，此图中两个点均不为割点，所以此图也属于BCC？

总之做题时注意题面要求，若要求的不含此种BCC则判断每个BCC的大小即可

无向连通图中割点一定属于至少两个BCC，非割点只属于一个BCC

有了上面的规定我们也不难理解这一条了：割点就算相邻也会属于至少两个BCC；BCC间的交点都是割点，所以非割点只属于一个BCC

到一个结点就将该结点入栈

为什么用栈存储呢？因为DFS是由上到下的，而分离BCC是自下而上的，需要后进先出的数据结构——栈

回溯时若目标结点low值不小于当前结点dfn值就出栈直到目标结点（目标结点也出栈），将出栈结点和当前结点存入BCC

对于每个BCC，它在DFS树中最先被发现的点一定是割点或DFS树的树根

证明：割点是BCC间的交点，故割点在BCC的边缘，且BCC间通过割点连接，所以BCC在DFS树中最先被发现的点是割点；特殊情况是对于开始DFS的点属于的BCC，其最先被发现的点就是DFS树的树根

上面的结论等价于每个BCC都在其最先被发现的点（一个割点或树根）的子树中

这样每发现一个BCC（low[v]>=dfn[u]），就将该子树出栈，并将该子树和当前结点（割点或树根）加入BCC中。上面的操作与此描述等价

（我就是因为这个条件“将子树出栈”没理解写错了结果调了一晚上poj2942）

综上，存点是不是很好理解？存边虽然不会涉及重复问题（割点属于至少两个BCC），但会有很多无用操作。个人觉得存点也是个不错的选择。

模板

#include<cstdio>

#include<cctype>

#include<vector>

using namespace std;

struct edge

{

    int to,pre;

}edges[];

int head[],dfn[],dfs_clock,tot;

int num;//BCC数量

int stack[],top;//栈

vector<int>bcc[];

int tarjan(int u,int fa)

{

    int lowu=dfn[u]=++dfs_clock;

    for(int i=head[u];i;i=edges[i].pre)

        if(!dfn[edges[i].to])

        {

            stack[++top]=edges[i].to;//搜索到的点入栈

            int lowv=tarjan(edges[i].to,u);

            lowu=min(lowu,lowv);

            if(lowv>=dfn[u])//是割点或根

            {

                num++;

                while(stack[top]!=edges[i].to)//将点出栈直到目标点

                    bcc[num].push_back(stack[top--]);

                bcc[num].push_back(stack[top--]);//目标点出栈

                bcc[num].push_back(u);//不要忘了将当前点存入bcc

            }

        }

        else if(edges[i].to!=fa)

            lowu=min(lowu,dfn[edges[i].to]);

    return lowu;

}

void add(int x,int y)//邻接表存边

{

    edges[++tot].to=y;

    edges[tot].pre=head[x];

    head[x]=tot;

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(x,y),add(y,x);

    }

    for(int i=;i<=n;i++)//遍历n个点tarjan

        if(!dfn[i])

        {

            stack[top=]=i;

            tarjan(i,i);

        }

    for(int i=;i<=num;i++)

    {

        printf("BCC#%d: ",i);

        for(int j=;j<bcc[i].size();j++)

            printf("%d ",bcc[i][j]);

        printf("\n");

    }

    return ;

}

简介

在阅读下列内容之前，请务必了解图论基础部分。

定义¶

割点和桥更严谨的定义参见图论基础。

在一张连通的无向图中，对于两个点u和v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说u和v边双连通。

在一张连通的无向图中，对于两个点u和v，如果无论删去哪个点（只能删去一个，且不能删和自己）都不能使它们不连通，我们就说u和v点双连通。

边双连通具有传递性，即，若x,y边双连通， y,z边双连通，则x,z边双连通。

点双连通不具有传递性，反例如下图， A,B点双连通， B,C点双连通，而 A,C不点双连通。

双连通分量（点-双连通分量&边-双连通分量）

DFS

对于一张连通的无向图，我们可以从任意一点开始 DFS，得到原图的一棵生成树（以开始 DFS 的那个点为根），这棵生成树上的边称作树边，不在生成树上的边称作 非树边 。

由于 DFS 的性质，我们可以保证所有非树边连接的两个点在生成树上都满足其中一个是另一个的祖先。

DFS 的代码如下：

void DFS(int p) {

 visited[p] = true;

 for (int to : edge[p])

   if (!visited[to]) DFS(to);

}

DFS 找桥并判断边双连通

首先，对原图进行 DFS。

双连通分量（点-双连通分量&边-双连通分量）

如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边覆盖了这条树上路径上所有的边。绿色的树边至少被一条非树边覆盖，黑色的树边不被任何非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

如何用算法去实现以上过程呢？首先有一个比较暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，这样的时间复杂度为O(nm) 。

怎么优化呢？可以用差分。对于每一条非树边，在其树上深度较小的点处打上 -1 标记，在其树上深度较大的点处打上 +1 标记。然后O(n)求出每个点的子树内部的标记之和。对于一个点u，其子树内部的标记之和等于覆盖了u和u的父亲之间的树边的非树边数量。若这个值非0，则u和u的父亲之间的树边不是桥，否则是桥。

用以上的方法O(n+m)求出每条边分别是否是桥后，两个点是边双连通的，当且仅当它们的树上路径中不包含桥。

DFS 找割点并判断点双连通¶

双连通分量（点-双连通分量&边-双连通分量）

如上图所示，黑色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径。

考虑一张新图，新图中的每一个点对应原图中的每一条树边（在上图中用蓝色点表示）。对于原图中的每一条非树边，将这条非树边对应的树上简单路径中的所有边在新图中对应的蓝点连成一个连通块（这在上图中也用蓝色的边体现出来了）。

这样，一个点不是桥，当且仅当与其相连的所有边在新图中对应的蓝点都属于同一个连通块。两个点点双连通，当且仅当它们在原图的树上路径中的所有边在新图中对应的蓝点都属于同一个连通块。

蓝点间的连通关系可以用与求边双连通时用到的差分类似的方法维护，时间复杂度。

【双连通分量】

一、边双连通分量定义

在分量内的任意两个点总可以找到两条边不相同的路径互相到达。总而言之就是一个圈，正着走反着走都可以相互到达，至少只有一个点。

二、点双连通分量的定义

参照上面，唯一的不同：任意两个点可以找到一条点不同的路径互相到达。也是一个圈，正反走都可以，至少为一个点。

三、边、点双连通分量模板代码要注意的地方

边双连通分量

1.每个节点的所有儿子遍历后才开始计算分量大小，请与点双连通相区分；

2.割顶只能属于一个分量，请与割边区分；（容易搞混）

3.要注意j是否是i的父节点；

上述几点如下：

void DFS(int i,int fd)//fd是父边

{

    low[i]=dfn[i]=++dfs_clock;

    vis[i]=;

    stk[++top]=i;//栈存节点

    for(int p=last[i];p;p=E[p].pre)

    {

        int j=E[p].to,id=E[p].id;

        if(vis[j])

        {

            if(dfn[j]<dfn[i]&&fd!=id) low[i]=min(low[i],dfn[j]);

            continue;

        }

        DFS1(j,id);

        low[i]=min(low[i],low[j]);

    }

    //所有儿子遍历完再求

    if(low[i]==dfn[i])

    {

        cc++;

        int x;

        while()

        {

            x=stk[top--];

            belong[x]=cc;

            size[cc]++;

            if(x==i) break;//注意是等于i才跳出，也就是i只能属于一个边连通分量

        }

        maxcc=max(maxcc,size[cc]);

    }

}

点双连通分量

1.每遍历一个儿子就计算是否有点连通分量；

2.割顶可以属于多个连通分量，请注意与割边区分；

3.当i为根节点时，至少要有两个儿子才能是割点；

上述几点如下：

void DFS(int i,int fd)//fd是父边

{

    low[i]=dfn[i]=++dfs_clock;

    stk[++top]=i;//栈存节点

    int chd=;//统计儿子数 

    for(int p=last[i];p;p=E[p].pre)

    {

        int j=E[p].to,id=E[p].id;

        if(dfn[j])

        {

            if(dfn[j]<dfn[i]&&id!=fd) low[i]=min(low[i],dfn[j]);

            continue;

        }

        chd++;

        DFS(j,id);

        low[i]=min(low[i],low[j]);

        if(low[j]>=dfn[i])//遍历完一个儿子就看是否有连通分量

        {

            cut[i]=;//初步判断i是割顶（还不一定，要看最后的条件）

            bcc_cnt++;

            bcc[bcc_cnt].push_back(i);//只是把i给存进去，而不存i属于哪个分量，因为i是割顶，可能也属于别的分量

            int x;

            while()

            {

                x=stk[top--];

                bcc[bcc_cnt].push_back(x);

                if(x==j) break;//注意到j结束

            }

        }

    }

    if(fd==&&chd==) cut[i]=;//这个结论应该都知道

}

【强连通分量】

一、定义

有向图上的环，不啰嗦，与上面两种类似，至少为一个点；

二、模板代码注意的地方

1.每个点所有儿子遍历完才开始求分量；（类似边双连通分量）

2.每个点只能属于一个分量；

void DFS(int i)

{

    low[i]=dfn[i]=++dfs_clock;

    stk[++top]=i;

    for(int p=last[i];p;p=E[p].pre)

    {

        int j=E[p].v;

        if(dfn[j])

        {

            if(!belong[j]) low[i]=min(low[i],dfn[j]);

            continue;

        }

        DFS(j);

        low[i]=min(low[i],low[j]);

    }

    if(dfn[i]==low[i])

    {

        scc++;

        while()

        {

            int x=stk[top--];

            belong[x]=scc;

            size[scc]++;

            if(x==i) break;

        }

    }

}

【强连通分量和双连通分量常见的模型和问法】

双连通分量

1.给出的图是非连通图，如：

a.有一些点，一些边，加最少的边，要使得整个图变成双联通图。

大致方法：求出所有分量，把每个分量看成一个点，统计每个点的度，有一个度为一则cnt加1，答案为（cnt+1）/2；

b.有一些点，一些边，问最少多少个点单着。

大致方法：求出所有的分量即可，但要注意不同的题可能有特殊要求（如圆桌骑士要求奇圈，要用到二分图判定）

c.各种变式问题

2.给出的图是连通图，如：

a.给定一个起点一个终点，求各种问题是否能实现。

大致方法：求出所有分量，并把每个分量当成点，于是问题得到化简；

b.给一个图，然后有大量的离线回答。

大致方法：求出所有分量，再求出上下子树的信息；

c.各种变式问题；

强连通分量

1.给出的是非连通图，如：

a.有一些点，一些有向边，求至少加多少边使任意两个点可相互到达

大致方法：求出所有的分量，缩点，分别求出出度入度为0的点的数量，取多的为答案；

b.有一些点，一些有向边，求在这个图上走一条路最多可以经过多少个点

大致方法：求出所有的分量，缩点，形成一个或多个DAG图，然后做DAG上的dp

c.有一些点，一些有向边，给出一些特殊点，求终点是特殊点的最长的一条路

大致方法：求出所有分量，并标记哪些分量有特殊点，然后也是DAG的dp

2.给出的是连通图，比较少，有也比较简单

总结

1.遇到非连通图几乎可以肯定是要求连通分量，不论是无向还是有向图；（可以节约大量思考时间）

2.凡是对边、点的操作，在同一个分量内任意一个点效果相同的，几乎都是缩点解决问题；再粗暴点，几乎求了连通分量都要缩点；

3.一定要考虑特殊情况，如整个图是一个连通分量等（考虑到了就有10-20分）；

4.对于双连通分量要分析是边还是点双连通分量；

5.拿到题目要先搞清楚给的是连通图还是非连通图。

POJ3694 Network

https://vjudge.net/problem/POJ-3694

problem

A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or indirectly by successive links, so data can be transformed between any two computers. The administrator finds that some links are vital to the network, because failure of any one of them can cause that data can't be transformed between some computers. He call such a link a bridge. He is planning to add some new links one by one to eliminate all bridges.

You are to help the administrator by reporting the number of bridges in the network after each new link is added.

Input

The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤ 200,000).
Each of the following M lines contains two integers A and B ( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B. Computers are numbered from 1 to N. It is guaranteed that any two computers are connected in the initial network.
The next line contains a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links the administrator plans to add to the network one by one.
The i-th line of the following Q lines contains two integer A and B (1 ≤ A ≠ B ≤ N), which is the i-th added new link connecting computer A and B.

The last test case is followed by a line containing two zeros.

Output

For each test case, print a line containing the test case number( beginning with 1) and Q lines, the i-th of which contains a integer indicating the number of bridges in the network after the first i new links are added. Print a blank line after the output for each test case.

Sample Input

Sample Output

Case 1:

1

0

Case 2:

2

0

大致翻译：给你N个点M条边的无向图，并且有Q次加边，问每次加边之后图中的桥的数量。

显然，如果加入的边的两个端点在同一个边双内，那么桥的数量不变。所以我们先用Tarjan对原图进行边双连通分量缩点得到一棵树。

接着，对于两个端点不在一个边双的情况，显然桥的数量减少量等于两个端点的树上距离。我们求出树上距离，然后把两端点之间的边标记起来，即边长由原来的1改成0。每次求树上距离时就先一个个地往上爬，顺便还可以标记边。时间复杂度为O(M+QN)，可以通过本题，但显然不优。

既然边长变成0了，我们以后都没必要再管这些边了，所以我们可以用缩树的办法，用并查集把两个端点之间的点合并到一个集合中去，然后下次爬到这两个端点处时直接跳到LCA的位置就好了。

题解

1.利用Tarjan算法，求出每个边双联通分量，并且记录每个点属于哪一个分量。

2.将每一个边双联通分量缩成一个点，最终得到一棵树。而我们想要得到一棵有根树，怎么办？其实在执行Tarjan算法的时候，就已经形成了一个有根树。所以我们只需要在Tarjan算法的基础上，再记录每一个点的父节点以及深度就可以了。

3.每次询问的时候，如果两个点在同一个分量中，那么他们的相连不会减少桥的个数。如果两个点在不同的分量中，那么u->LCA(u,v)和v->LCA(u,v)上路径上的桥，都可以减少，路径上的点都可以缩成一个点，即合并成一个分量。

对于缩点的处理：

　　方法一：对于一个分量，可以设置一个点为实点，其余的点为虚点。实点即代表着这个分量的所有信息，虚点虽然属于这个分量的点，但是却对他视而不见。我们要做的，就是在这个分量里选择一个点，去代表整个分量。

　　方法二：同样地，我们也需要为每一个分量选出一个代表，以表示这个分量。与方法一的“视而不见”不同的是，方法二对每一个点都设置了一个归属集合，即表示这个点属于哪一个集合。由于在处理的过程中，一个集合可能又会被另一个集合所包含，所以我们可以利用并查集的路径压缩，很快地找到一个点的最终所属集合。

方法一：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <string>

#include <set>

#define ms(a,b) memset((a),(b),sizeof((a)))

using namespace std;

typedef long long LL;

const double EPS = 1e-;

const int INF = 2e9;

const LL LNF = 2e18;

const int MAXN = 1e5+;

struct Edge

{

    int to, next;

}edge[MAXN*];

int tot, head[MAXN];

int index, dfn[MAXN], low[MAXN];

int isbridge[MAXN], sum_bridge;

int fa[MAXN], depth[MAXN];

void addedge(int u, int v)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void Tarjan(int u, int pre)

{

    dfn[u] = low[u] = ++index;

    depth[u] = depth[pre] + ;  //记录深度

    fa[u] = pre;        //记录父亲结点

    for(int i = head[u]; i!=-; i = edge[i].next)

    {

        int v = edge[i].to;

        if(v==pre) continue;

        if(!dfn[v])

        {

            Tarjan(v, u);

            low[u] = min(low[u], low[v]);

            if(low[v]>dfn[u])   //isbridge[v]表示在树中，以v为儿子结点的边是否为桥

                isbridge[v] = , sum_bridge++;

        }

        else

            low[u] = min(low[u], dfn[v]);

    }

}

void LCA(int u, int v)

{

    if(depth[u]<depth[v]) swap(u, v);

    while(depth[u]>depth[v])    //深度大的先往上爬。遇到桥，就把它删去。

    {

        if(isbridge[u]) sum_bridge--, isbridge[u] = ;

        u = fa[u];

    }

    while(u!=v) //当深度一样时，一起爬。遇到桥，就把它删去。

    {

        if(isbridge[u]) sum_bridge--, isbridge[u] = ;

        u = fa[u];

        if(isbridge[v]) sum_bridge--, isbridge[v] = ;

        v = fa[v];

    }

}

void init()

{

    tot = ;

    memset(head, -, sizeof(head));

    index = ;

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    memset(isbridge, , sizeof(isbridge));

    sum_bridge = ;

}

int main()

{

    int n, m, kase = ;

    while(scanf("%d%d", &n, &m) && (n||m) )

    {

        init();

        for(int i = ; i<=m; i++)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            addedge(u, v);

            addedge(v, u);

        }

        depth[] = ;

        Tarjan(, );

        int q, a, b;

        scanf("%d", &q);

        printf("Case %d:\n", ++kase);

        while(q--)

        {

            scanf("%d%d", &a, &b);

            LCA(a, b);

            printf("%d\n", sum_bridge);

        }

        printf("\n");

    }

}

方法二：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <string>

#include <set>

#define ms(a,b) memset((a),(b),sizeof((a)))

using namespace std;

typedef long long LL;

const double EPS = 1e-;

const int INF = 2e9;

const LL LNF = 2e18;

const int MAXN = 1e6+;

struct Edge

{

    int to, next;

}edge[MAXN], edge0[MAXN];   //edge为初始图， edge0为重建图

int tot, head[MAXN], tot0, head0[MAXN];

int index, dfn[MAXN], low[MAXN];

int top, Stack[MAXN], instack[MAXN];

int belong[MAXN];

int fa[MAXN], depth[MAXN];  //fa用于重建图时记录当前节点的父亲节点，depth记录当前节点的深度

int sum_bridge;

//找到x最终所属的结合

int find(int x) { return belong[x]==x?x:belong[x]=find(belong[x]); }

void addedge(int u, int v, Edge edge[], int head[], int &tot)

{

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void Tarjan(int u, int pre)

{

    dfn[u] = low[u] = ++index;

    Stack[top++] = u;

    instack[u] = true;

    for(int i = head[u]; i!=-; i = edge[i].next)

    {

        int v = edge[i].to;

        if(v==pre) continue;

        if(!dfn[v])

        {

            Tarjan(v, u);

            low[u] = min(low[u], low[v]);

            if(low[v]>dfn[u]) sum_bridge++;

        }

        else if(instack[v])

            low[u] = min(low[u], dfn[v]);

    }

    if(dfn[u]==low[u])

    {

        int v;

        do

        {

            v = Stack[--top];

            instack[v] = false;

            belong[v] = u;  //把集合的编号设为联通分量的第一个点

        }while(v!=u);

    }

}

void build(int u, int pre)

{

    fa[u] = pre;    //记录父亲节点

    depth[u] = depth[pre] + ;  //记录深度

    for(int i  = head0[u]; i!=-; i=edge0[i].next)

        if(edge0[i].to!=pre)    //防止往回走

            build(edge0[i].to, u);

}

int LCA(int u, int v)   //左一步右一步地找LCA

{

    if(u==v) return u;  //因为两个结点一定有LCA， 所以一定有u==v的时候

    //可能爬一步就爬了几个深度，因为中间的结点已经往上缩点了

    if(depth[u]<depth[v]) swap(u, v);   //深度大的往上爬

    sum_bridge--;

    int lca = LCA(find(fa[u]), v);

    return belong[u] = lca;     //找到了LCA，在沿路返回的时候把当前节点的所属集合置为LCA的所属集合

}

void init()

{

    tot = tot0 = ;

    memset(head, -, sizeof(head));

    memset(head0, -, sizeof(head0));

    index = top = ;

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    memset(instack, , sizeof(instack));

    sum_bridge = ;

}

int main()

{

    int n, m, kase = ;

    while(scanf("%d%d", &n, &m) && (n||m) )

    {

        init();

        for(int i = ; i<=m; i++)

        {

            int u, v;

            scanf("%d%d", &u, &v);

            addedge(u, v, edge, head, tot);

            addedge(v, u, edge, head, tot);

        }

        Tarjan(, );

        for(int u = ; u<=n; u++)   //重建建图

        for(int i = head[u]; i!=-; i = edge[i].next)

        {

            int tmpu = find(u);

            int tmpv = find(edge[i].to);

            if(tmpu!=tmpv)

                addedge(tmpu, tmpv, edge0, head0, tot0);

        }

        depth[find()] = ;

        build(find(), find());    //把无根树转为有根树

        int q, a, b;

        scanf("%d", &q);

        printf("Case %d:\n", ++kase);

        while(q--)

        {

            scanf("%d%d", &a, &b);

            LCA(find(a), find(b));

            printf("%d\n", sum_bridge);

        }

        printf("\n");

    }

}

题目大意：n个点的无向图初始化有m条边

之后q次操作每次表示在点a与点b间搭建一条边输出对于q次操作每次剩下的桥的条数

初始化可以用tarjan算法求出桥对于不是割边的两个点就可以算是在一个集合中这样用并查集就可以进行缩点

最后生成的就是一棵树树边就是图中的所有桥 q次询问中每次加边<u,v> 如果u和v在一个集合中说明新的边不会造成影响

如果u和v在两个集合中两个集合间的边在添加<u,v>后就会失去桥的性质这样通过LCA就可以遍历所有两个集合间的集合在加上<u,v>这条边后这两个集合间的集合其实就变成了一个环也就是可以缩成一个点在合并集合的过程中就可以把消失的桥从总和中减去了

之前一直在想为什么要用LCA来做这道题，原来他们缩点之后会形成一棵树，然后因为已经经过缩点了，所以这些树上的边都是桥（终于理解为什么他们说缩点之后的树边为桥了），那么如果加入的这条边是属于一个缩点的话（缩点里面的点算是一个集合）那么就对原图中的桥没有任何影响，但是如果加入的边是属于两个缩点的话，那么就会形成一个环，那么任意删除这个环里面的一条边，这棵树还是互通的。ORZ终于理解了，那么就可以利用LCA的特性去算出到底减少了多少条桥了，因为是最近公共祖先，那么新加入的这条边的两个点通过LCA找到对方肯定是走最短的路径（在树上走最小的边）那么就可以得到结果了，总桥数减去走LCA上的边就是题目要的答案了！！！！

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stack>

using namespace std;

#define N 100010

#define M 400010

struct edge{

    int v;

    int next;

}Edge[M];//边的集合

int node[N];//顶点集合

int DFN[N];//节点u搜索的序号(时间戳)

int LOW[N];//u或u的子树能够追溯到的最早的栈中节点的序号(时间戳)

int fa[N];//上一个节点

int pre[N];//并查集父亲节点

int n,m;//n：点的个数；m：边的条数

int cnt_edge;//边的计数器

int Index;//序号(时间戳)

int ans;//桥的个数 

void init()//初始化,注意不要把n初始为0

{

    cnt_edge=;

    Index=;

    ans=;

    memset(Edge,,sizeof(Edge));

    memset(node,-,sizeof(node));

    memset(DFN,,sizeof(DFN));

    memset(LOW,,sizeof(LOW));

    memset(fa,,sizeof(fa));

    memset(pre,,sizeof(pre));

    for(int i=;i<=n;i++)

    {

        pre[i]=i;

    }

}

int Find(int x)

{

//    while(n!=pre[n])//写成这样会出错

//    {

//        n=pre[n];

//    }

//    return n;

    return pre[x] == x? pre[x]: (pre[x] = Find(pre[x]));

}

int Union(int u,int v)

{

    int uu,vv;

    uu=Find(u);

    vv=Find(v);

    if(vv==uu)

        return ;

    pre[uu]=vv;

    return ;

}

void add_edge(int u,int v)//邻接表存储

{

    Edge[cnt_edge].next=node[u];

    Edge[cnt_edge].v=v;

    node[u]=cnt_edge++;

}

void tarjan(int u)

{

    DFN[u]=LOW[u]=Index++;

    for(int i=node[u];i!=-;i=Edge[i].next)

    {

        int v=Edge[i].v;

        if(v==fa[u]) //这个要写前面

            continue;

        if(!DFN[v])//如果点v没被访问

        {

            fa[v]=u;

            tarjan(v);

            LOW[u]=min(LOW[u],LOW[v]);

            if(LOW[v]>DFN[u])

            {

                ans++;

            }

            else Union(v,u);

        }

        else //if(v!=fa[u]) //如果点v已经被访问过

            LOW[u]=min(LOW[u],DFN[v]);

    }

}

void LCA(int u,int v)

{

    if(DFN[v]<DFN[u])

        swap(u,v);

    while(DFN[v]>DFN[u])

    {

        if(Union(v,fa[v]))

            ans--;

        v=fa[v];

    }

    while(v!=u)

    {

        if(Union(u,fa[u]))

            ans--;

        u=fa[u];

    }

}

int main()

{

    //freopen("sample.txt","r",stdin);

    int tot=;

    while(~scanf("%d %d",&n,&m)&&(m+n))

    {

        init();

        while(m--)

        {

            int u,v;

            scanf("%d %d",&u,&v);

            add_edge(u,v);

            add_edge(v,u);

        }

        fa[]=;

        for(int i=;i<=n;i++)

        {

            if(!DFN[i])

            {

                tarjan(i);

            }

        }

        int q;

        scanf("%d",&q);

        printf("Case %d:\n",++tot);

        while(q--)

        {

            int u,v;

            scanf("%d %d",&u,&v);

            LCA(u,v);

            printf("%d\n",ans);

        }

        printf("\n");

    }

    return  ;

}

【POJ 3177】Redundant Paths（Tarjan求桥、边双连通分量）

Description

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

Input

Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

Output

Line 1: A single integer that is the number of new paths that must be built.

Sample Input

Sample Output

Hint

Explanation of the sample:

Check some of the routes:
1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7
Every pair of fields is, in fact, connected by two routes.

It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.

　　【题意】

[求一个无向图中还需加入多少条边能构成一个边双连通分量]

　　【题解】

看起来很厉害的样子，其实还是先用Tarjan缩点，然后，枚举每一条边，看左右两个端点缩点后是否在同一个点中，如果不在连边，其实只要更新每点的度即可，最后统计度为1的点的个数ans,由求“加入多少条边能构成一个边双连通分量”的方法可知，答案为(ans+1)/2。

双连通分量（点-双连通分量&边-双连通分量）

概念：

点双连通和边双连通

概述

性质

算法

理解

模板

简介

定义¶

DFS

DFS 找桥并判断边双连通

DFS 找割点并判断点双连通¶

【双连通分量】

一、边双连通分量定义

二、点双连通分量的定义

边双连通分量

点双连通分量

【强连通分量】

一、定义

二、模板代码注意的地方

【强连通分量和双连通分量常见的模型和问法】

双连通分量

强连通分量

总结

POJ3694 Network

problem

Input

Output

Sample Input

Sample Output

题解

【POJ 3177】Redundant Paths（Tarjan求桥、边双连通分量）

Description

Input

Output

Sample Input

Sample Output

Hint

【题意】

【题解】

相关文章

　　【题意】

　　【题解】