强连通分量

一、定义

　　连通分量：在无向图中，即为连通子图。

　　有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)(百度百科)

　　极大强连通子图：G是一个极大强连通子图，当且仅当G是一个强连通子图且不存在另一个强连通子图G’，是得G是G'的真子集

二、Kosaraju算法

　　时间复杂度：O（n+m）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)

using namespace std;

const int N=100,M=200;
int n,m,cnt,num_edge,head1[N+1],head2[N+1],d[N+1];
struct Edge{
    int next,from,to;
}edge1[M+1],edge2[M+1];
bool vis[N+1];
inline void Add_edge(int from,int to)
{
    edge1[++num_edge]=(Edge){head1[from],from,to};
    edge2[num_edge]=(Edge){head2[to],to,from};
    head1[from]=num_edge,head2[to]=num_edge;
}
void Dfs1(int u)
{
    for(int i=head1[u];i;i=edge1[i].next)
        if(!vis[edge1[i].to])
            d[++cnt]=edge1[u].to,vis[edge1[i].to]=1,Dfs1(edge1[i].to);
}
void Dfs2(int u)
{
    for(int i=head2[u];i;i=edge2[i].next)
        if(!vis[edge2[i].to])
            vis[edge2[i].to]=1,Dfs2(edge2[i].to);
}
int Kosaraju()
{
    FORa(i,1,n)
        if(!vis[i])
            d[++cnt]=i,vis[i]=1,Dfs1(i);
    memset(vis,0,sizeof(vis)),cnt=0;
    FORs(i,n,1)
        if(!vis[d[i]])
            ++cnt,vis[i]=1,Dfs2(d[i]);
    return cnt;
}
int main()
{
    int x,y;
    scanf("%d%d",&n,&m);
    FORa(i,1,m)
    {
        scanf("%d%d",&x,&y);
        Add_edge(x,y);
    }
    printf("%d",Kosaraju());
    return 0;
}
/*
12
16
12 11
11 8
11 10
8 10
10 9
9 8
9 7
7 6
5 7
6 5
6 4
6 3
4 3
2 3
3 2
4 1
*/

三、Tarjan算法

　　1.基本概念

　　　　树枝边

　　　　前向边

　　　　后向边

　　　　横叉边

　　2.主要流程

　　3.流程演示

　　4.操作原理：

　　　　Tarjan算法基于定理：在任何深度优先搜索中，同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。
　　　　可以证明，当一个点既是强连通子图Ⅰ中的点，又是强连通子图Ⅱ中的点，则它是强连通子图Ⅰ∪Ⅱ中的点。
　　　　这样，我们用low值记录该点所在强连通子图对应的搜索子树的根节点的Dfn值。注意，该子树中的元素在栈中一定是相邻的，且根节点在栈中一定位于所有子树元素的最下方。
　　　　强连通分量是由若干个环组成的。所以，当有环形成时（也就是搜索的下一个点已在栈中），我们将这一条路径的low值统一，即这条路径上的点属于同一个强连通分量。
　　　　如果遍历完整个搜索树后某个点的dfn值等于low值，则它是该搜索子树的根(根的编号最小，大家都统一为它，没有被统一的，也就是把别人统一的，就是根)。这时，它以上（包括它自己）一直到栈顶的所有元素组成一个强连通分量。

int DFN[maxn],LOW[maxn],index;//序号及环开头的序号
int S[maxn],top;//手写栈
bool ins[maxn];//是否进栈
int col[maxn],numc;//染色
void Tarjan(int u){
    DFN[u] = LOW[u] = ++index;
    S[++top] = u;//进栈
    ins[u] = true;
    for(int i = head[u];i;i = E[i].nxt){
        int v = E[i].v;
        if(!DFN[v]){
            Tarjan(v);
            LOW[u] = min(LOW[u],LOW[v]);//找爸爸（环开头）最小的
            }
        else if(ins[v]){
            LOW[u] = min(LOW[u],DFN[v]);//判断谁是爸爸
            }
        }
    if(DFN[u] == LOW[u]){//发现更新完一轮自己是爸爸
        numc++;
        while(S[top + 1] != u){
            col[S[top]] = numc;//出栈，染色
            ins[S[top--]] = false;
            }
        }
    }

强连通分量

一、定义

二、Kosaraju算法

三、Tarjan算法

1.基本概念

2.主要流程

3.流程演示

4.操作原理：

四：用途

1.有向图的缩点

2.解决2-SAT问题

五、相关文章