图的连通性问题

图论

1.连通图与非连通图
连通图：如果无向图中任意一对顶点都是连通的，称此图为连通图
非连通图：如果一个不是连通图就是非连通图
连通分量（连通分支）：非连通图的极大连通子图

//遍历所有顶点并求连通分量个数
int subnets = 0; //表示连通分量个数的变量
for(int k = 0; k < n; k ++)
{
    if( !vis[k] ) //顶点k未被访问过
    {
        dfs( k ); //从顶点k出发进行dfs
        subnets++;
    }
}

2.无向图的点连通性
点连通性：与顶点有关的连通性

1)割顶集与顶点的连通度
割顶集：V'是V的子集，而删除V'及与V'关联的边后图不连通
极小割顶集：割顶集V'的任何真子集都不是割顶集
最小割顶集：顶点个数最小的极小割顶集称为最小割顶集

顶点连通度K(G):最小割顶集中的顶点的个数
等价于删除的最少点使图G不连通的这个点的个数

割点：如果割点集中只有一个顶点，该顶点就被称为割点
等价于删除该顶点和该顶点相连的边之后连通分量的数量增加

点双连通图：如果一个无向连通图 G 没有割点，或者说点连通度 κ(G)>1，则称 G为点双连通图，或者称为重连通图。
点双连通分量：一个连通图 G 如果不是点双连通图，那么它可以包括几个点双连通分量，也称为重连通分量（或块）。

• 割点求解的方法

1）朴素算法(根据定义)O(n^3)

把选择的节点和其相连的边标记掉，每次暴搜全图。

2）Tarjian算法O(n^2)

朴素算法里面我们要从每个顶点出发搜全图一边，而Tarjian算法只需要从某个顶点出发进行一次遍历就可以求出所有割点。
我们对图G的每个顶点u定义一个low值，low[u]记录的是从u或者u的子孙从出发通过回边可以到达的最低深度优先数。

low[u] = min
{
    dfn[u],//自身深度优先数
    min{ low[w] | w是u的一个子女 }，//子女顶点w的low[w]的最小值
    min{ dfn[v] | v与u邻接， 且(u，v)是一条回边 }//可以直接通过回边到达的最低优先数
}

所以u是割点的充要条件是：
1.u是具有连个以上子女的深度优先生成树的根
或
2.不是根但是有一个子女w,使得low[w] >= dfn[v]。

用一个题来讲讲这个算法在代码实现中要解决的几个细节
(1)如何判断顶点v是顶点u的祖先结点
(2)如何判断边(v，u)是回边
(3)如何判断顶点v是顶点u的儿子结点
poj1523

void dfs(int u)
{
    for (int v = 1; v <= nodes; v++)
    {
        /*
            v和u邻接。在生成树中是两种情况
            1. v是u的祖先结点，这样(v,u)就是一条回边
            2. v是u的儿子结点
        */
        if(edge[u][v])
        {
            if(!vis[v])
            {
                vis[v] = 1;
                tmpdfn++;
                dfn[v] = low[v] = tmpdfn;
                dfs( v ); // dfs执行完毕后，low[v]值已经求出
                //回退的时候，计算顶点u的low值
                low[u] = min ( low[u], low[v] );
                if( low[v] >= dfn[u] )
                {
                    if( u != 1)
                        subnets[u]++; // 去掉该节点后的连通分量的个数
                //根结点的子女结点的个数(如果大于2，则根结点是割点)
                    if( u == 1) 
                        son++;
                }
            }
            //此前v已经访问过了，v是u的祖先结点((v,u)就是一条回边）
            else 
            {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
}

3.无向图的边连通性
定义和上面相似
割边集：在 G 中删去 E'后图不连通
边数最小的极小割边集称为最小割边集。最小割边集中边的个数，称作图 G 的边连通度
割边又称做桥
割边求法思想和上面完全相同就不再赘述了

边双连通图：如果一个无向连通图 G 没有割边，则称 G 为边双连通图。
边双连通分量：一个连通图的边双连通分量是该图的极大重连通子图，在边双连通分量中不存在割边。在连通图中，把割边删除，则连通图变成了多个连通分量，每个连通分量就是一个边双连通分量。

4.无向图顶点连通性和边连通性的关系
1)顶点的连通度和边的连通度的关系
顶点的连通度 <= 边的连通度 <= 最小度

2)割边和割点的关系
与割边相连的点的度数大于等于2时该点是割点

5.有向图的连通性
有向图的连通性分为强连通、单连通、和弱连通。
强连通有向图：对于图G中的任意两个节点u，v，既存在v到u的路径又存在u到v的路径
强连通分量：非强连通图的极大连通子图
单连通有向图：对于图G中的任意两个节点u，v，存在v到u的路径或存在u到v的路径
弱连通有向图：忽略方向后的无向连通图
所以说是强连通图就一定是单连通 有向图一定是弱连通图

有向图强连通分量的求解方法
1)Tarjan算法O(n+m)

伪代码：

tarjan( u )
{
    dfn[u] = low[u] = ++tmpdfn; //结点u的dfn和low的初值
    stack.push( u )             //将u入栈
    for each( u, v) in E        //枚举每一条边
        if ( v is not visited)  //如果结点v没被访问过
            tarjan( v )         //继续向下找
            low[u] = min ( low[u], low[v])
        else if (v in stack)    //如果结点v还在栈内
            low[u] = min ( low[u], dfn[v])
    if( dfn[u] == low[u])       //如结点u是强连通分量的根
        repeat
            v = stack.pop
            print v
        until (u == v)    //将v退栈，为该强连通分量中的一个顶点
}

原理：Tarjan 算法是基于 DFS 算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索
树中未处理的节点加入一个栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。当
dfn(u)=low(u)时，以 u 为根的搜索子树上所有节点是一个强连通分量

例题： poj3160 Tarjan+DP

2)Kosaraju算法O(n+m)两次dfs对非强连通块的过滤算法
原理：如果有向图G的一个子图G’是强连通子图，那么各边反向后对没有任何影响，G'内各顶点仍然连通，G'仍然是强连通子图。然如果子图是单项连通的，反向后某些顶点就不连通了。

算法步骤：

Kosaraju算法步骤：
Step1、对有向图G做dfs，记录每个结点结束访问的时间(时间戳)(即节点出栈顺序，后出栈的点第二次先扫描)
Step2、将图G逆置，即将G中所有弧反向。
Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs
Step4、得到的遍历森林中每棵树对应一个强连通分量。

主要应用：缩点

例题：poj2186 bzoj2438