图的连通性问题--点的/边的双联通分量（没理解）

一.基本概念

1.割点：无向图中，一个点，去掉该点之后，图不再联通（分为>=2的几个连通分量），该点就是割点

2.桥：也叫做割边，去掉该边之后，图不再联通。

3.点的双连通图：针对的是无向图，没有割点的无向图就是点的双连通图

4.点的双连通分量：也叫做重连通分量（块），就是图中的一个不含有割点的连通分量。也就是去掉任何一个点，都可以连通的无向图分量

5.边的双连通图：这种图中的任意一对顶点至少存在两条无公共边的路径（可能有公共的顶点）。

6.边的双连通分量：不存在桥的连通分量（无向图中），如果在连通图中，把桥都删除的话，连通图就会变成了多个连通分量，每个连通分量都是一个双连通分量。

也就是去掉任意一条边后，仍然连通的无向图分量

7.桥与割点的关系：如果一个点连接着桥，那么这个点至少连接2个桥，才是割点。

二;Tarjan求解重连通分量（点的双连通分量）：

方法：Tarjan找到一个割点（dfn[u]<=low[v]），把边从栈顶一条条取出，直到遇到边（u,v）（这条边也是），要防止访问过的重新入栈。

注意：求强连通分量入栈的是点，而这时入栈的是边。

例题：输出无向图的各个连通分量

输入n，m，m条边，m行，输入u，v，输出连通分量。

对于一个图，输出uv表示边，一行为一个双连通分量，每一个图处理完后，输出一个空行。

输入：

7 9
1 2
1 3
1 6
1 7
2 3
2 4
2 5
4 5
6 7
4 4
1 2
2 3
3 4
4 1
0 0

输出：

5-2 4-5 2-4

3-1 2-3 1-2

7-1 6-7 1-6

4-1 3-4 2-3 1-2

 1 #include<iostream>
 2 using namespace std;
 3 #include<cstdio>
 4 #include<cstring>
 5 #define MAXN 20
 6 #define MAXM 40
 7 struct Edge{
 8     int u,v;
 9     void output()
10     {printf("%d-%d",u,v);}
11     int comp(Edge &t){return (u==t.u&&v==t.v)||(u==t.v&&v==t.u);}
12         
13 }; 
14 Edge edges[MAXM];
15 int se=0;
16 int contact[MAXN][MAXN];
17 int visited[MAXN];
18 int n,m;
19 int tmp=0;
20 int dfn[MAXN],low[MAXN];
21 void dfs(int u);
22 int main()
23 {
24     int number=1;
25     while(1)
26     {
27         scanf("%d%d",&n,&m);/*输入n个点，m条边*/
28         if(n==0&&m==0) break;
29         memset(contact,0,sizeof(contact));
30         for(int i=1;i<=m;++i)
31         {
32             int u,v;
33             scanf("%d%d",&u,&v);
34             contact[u][v]=contact[v][u]=1;/*contact记录u--v是否连通，是否已经在一个双连通分量中了*/
35         }
36         if(number>1)cout<<endl;
37         number++;
38         low[1]=dfn[1]=1;
39         tmp=1;
40         memset(visited,0,sizeof(visited));
41         visited[1]=1;
42         memset(edges,0,sizeof(edges));
43         se=-1;
44         dfs(1);/*从1开始深搜*/
45     }
46     return 0;
47 }
48 void dfs(int u)
49 {
50     for(int v=1;v<=n;++v)
51     {
52         if(contact[u][v]==1)/*找到与u相连的点*/
53         {
54             Edge t;
55             t.u=u;
56             t.v=v;/*储存当前边的信息*/
57             edges[++se]=t;
58             contact[u][v]=contact[v][u]=2;/*标记这条边已经被访问了*/
59             if(!visited[v])
60             {
61                 visited[v]=1;
62                 tmp++;
63                 dfn[v]=low[v]=tmp;
64                 dfs(v);
65                 low[u]=min(low[u],low[v]);
66                 if(low[v]>=dfn[u])/*如果u是一个割点*/
67                 {
68                     bool firstedge=true;
69                     while(1)
70                     {
71                         if(se<0) break;
72                         if(firstedge) firstedge=false;
73                         else printf(" ");
74                         Edge t1;
75                         t1=edges[se];
76                         t1.output();
77                         edges[se].u=edges[se].v=0;
78                         se--;
79                         if(t1.comp(t))break; 
80                      } 
81                      printf("
"); 
82                 }
83             }
84             else low[u]=min(low[u],dfn[v]);
85         }
86     }
87 }

View Code

三：边的双连通分量的求解

与点的双连通分量的求解相比，边的更为简单，求出途中的所有桥之后，把桥删除，那么原图就变成了多个联通块，每个连通块就是一个双连通分量，

桥不属于任何一个边双连通分量，其余的边和每个顶点，都属于且只属于一个边连通分量