连通性&割顶&桥&双连通&强连通&tarjan。。。

2018-04-24 09:23:30


概念:

连通分量:

连通:在无向图中,若从Vi到Vj有路径,则称Vi和Vj是连通的,而无向图有自反性、对称性和传递性,因此此时Vj和Vi也是连通的。

连通分量:

Connected Component,相互可达的结点集合。

连通图:

在无向图G中,若任意两个不同的顶点都连通,则G为连通图。

割顶和桥:

割顶:

Cut Vertex,对于无向图G,如果删除某个顶点u后,连通分量数目增加,则u便是图G的关节点(Articulation Vertex)或割顶。

桥:

Bridge,如果删除某条边,G就非连通了,这条边就称之为桥。

时间戳:

记录全局的当前时间。每个点访问的时间戳可以表示出各个点的访问顺序。

反向边

第一次处理时,从后代指向祖先的边称为反向边。

双连通分量:

点-双连通:

对于一个连通图,如果任意两点至少存在两条“点不重复”的路径, 则说这个图是点-双连通的(一般简称为双连通,Biconnected)

任意两条边都在同一个简单环内,即内部无割顶

边-双连通:

任意两点至少存在两条“边不重复”的路径(Edge-biconnected)

每条边都至少在一个简单环中,即所有边都不是桥

双连通分量:

对于无向图,点-双连通的极大子图成为双连通分量(Biconnected Component,BCC)或块(Block)

每条边恰好属于一个双连通分量

不同连通分量可能会有公共点(最多也只有一个公共点),这也就是割顶

任意一个割顶都是至少两个不同双连通分量的公共点

边-双连通分量:

边-双连通的极大子图

桥不属于任何一个边-双连通分量

其他边恰好属于一个边-双连通分量

点-双连通分量:{A,C,D}和{B,C,E}

边-双连通分量:{A,C,B,E,D}

强连通

强联通:在有向图中,若Vi到Vj有路径,Vj到Vi也有路径,则叫Strongly Connected Component, SCC。

强连通分量:强联通的极大子图

TIP:双连通为无向图,强连通为有向图



程序

几个数组的概念:

pre:记录当前节点的时间戳

low:low[x]为x及其后代所能通过反向边连回的最早的祖先的pre值

则若节点u的子节点v的low[v]≤pre[u],u是割顶

若low[v]>pre[u],即v的后代只能连回v自己,那么只需删除(u,v)这条边就可以让G非连通了,这条边就是桥。当然u也是割点

求割顶和桥:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,cnt=0,tot=0,num=0;
int head[200100],nxt[200100],to[200100];
int low[100100],f[100100],pre[100100];
void addedge(int x,int y)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void dfs(int u,int fa)
{
    int ch=0; 
    low[u]=pre[u]=++tot;
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(!pre[v])//若v还未访问过
        {
            ch++;
            dfs(v,u);//继续dfs求出low[v]
            low[u]=min(low[u],low[v]);
            if(low[v]>=pre[u]) f[u]=1;//low[v]>=pre[u] 则为割顶
            if(low[v]>pre[u]) num++;//low[v]>pre[u] 则为割顶
        }
        else if(pre[v]<pre[u] && v!=fa) low[u]=min(low[u],pre[v]);//v已经访问过,并且比u先访问到,如果不是u的父亲节点,low[u]就可以更新
    }
    if(fa==0 && ch==1) f[u]=0;//若u为根节点并且只有一个子节点把根节点去掉不会多出连通分量,所以u不为割顶
}
int main()
{
    while(1)
    {
        memset(f,0,sizeof(f));
        memset(pre,0,sizeof(pre));
        memset(low,0,sizeof(low));
        memset(head,-1,sizeof(head));
        cnt=0,tot=0,num=0;
        scanf("%d%d",&n,&m);
        if(!n && !m) break;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        for(int i=1;i<=n;i++)
            if(!pre[i]) dfs(i,0);
        int ans=0;
        for(int i=1;i<=n;i++)
            if(f[i]) ans++;
        cout<<ans<<" "<<num<<endl;//ans是割顶数量,num是桥的数量
        for(int i=1;i<=n;i++)
            if(f[i]) cout<<i<<endl;
    }
    return 0;
}

求双联通分量

代码其实差不多,这种方法求双联通分量叫做tarjan

int bcc_cnt; //点_双连通分量的数目
int belong[maxn];     //节点属于的点_双连通分量的编号
vector<int> G[maxn], bcc[maxn]; //点_双连通分量
int tarjan(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock, child = 0;
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];  Edge e = Edge(u, v);
        if (!pre[v])
        {
            s.push(e);  child++;
            int lowv = tarjan(v, u);   lowu = min(lowu, lowv); //用后代更新lowu
            if(lowv >= pre[u])
            {
                iscut[u] = true;   bcc_cnt++;  bcc[bcc_cnt].clear();
                while(1)
                {
                    Edge x = s.top(); s.pop();
                    if (belong[x.u] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.u);//x.u在第bbc_cnt个双连通分量中 
                        belong[x.u] = bcc_cnt;//x.u所在的双连通分量的编号是bcc_cnt 
                    }
                    if (belong[x.v] != bcc_cnt)
                    {
                        bcc[bcc_cnt].push_back(x.v);
                        belong[x.v] = bcc_cnt;
                    }
                    if (x.u == u && x.v == v) break;
                }
            }
        }
        else if (pre[v] < pre[u] && v != fa)
        {
            s.push(e);
            lowu = min(lowu,pre[v]);
        }
    }
    if (fa < 0 && child == 1) iscut[u] = 0;
    return lowu;
}

求强联通分量

代码其实也差不多一样,而且算法也叫tarjan。。。总之Tarjan是个很六的人

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans=0;
int sta[200001],top=0;
int dfn[200001],low[200001],tot=0;
int head[200001],nxt[200001],to[200001],cnt=0;
int f[200001];
void addedge(int x,int y)//邻接链表存图
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void tarjan(int u)//tarjan求强联通分量
{
    f[u]=1;
    dfn[u]=low[u]=++tot;
    sta[++top]=u;//入栈
    for(int i=head[u];i!=0;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(f[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        ans++;
        do
        {
            f[sta[top]]=0;
        }while(sta[top--]!=u);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        addedge(i,a);//加边,是有向边,别加两次
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    cout<<ans;//强连通分量的数量
    return 0;
}