前言:

近日回顾去年各位大佬的课件,发现什么都不会…(靠,大佬去年比我今年还强)然后对着现充fyy的课件一看一下午,终于搞懂一点有关联通分量的有关东西

前置知识:(拷自fyy课件)

  1. 强连通分量(SCC):
    >在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。
  2. ….

其他什么的知识点就不讲了直接开始求实际的东西,要用到的我看着说.然后kosaraju算法我也不说了,没有tarjan强,也没有他好用…(%%%tarjan老爷爷)

有向图求强连通分量

对于图G的每个点,记录下每个点的dfs序(dfn)和以它为根的搜索树中所能到达节点的dfn的最小值(low).
对于一个点u,它指向的点v分为三种情况.
1. v已经被访问过,且是它的祖先\tolow[u]=min(low[u],dfn[v])
2. v已经被访问过,不是它的祖先\to不在同一个强连通分量中,跳过
3. v尚未被访问过,向下dfs,low[u]=min(low[u],dfn[v]).

当点u的dfn=low,意味着以这个点为根的子树中不存在可以指向u的祖先。那么u到可以到达u的最深的孩子构成一个强连通分量。用一个栈O(V)维护这些信息。
复杂度显然也是O(V+E)….
(这种东西看分析是看不懂的直接看代码,磨一磨就好了)

代码:

void dfs(int now)//now是当前点
{
    vis[now]=1;st.push(now);//st是栈
    dfn[now]=low[now]=++num;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to]) dfs(to),low[now]=min(low[now],low[to]);
        else if(!scc[to]) low[now]=min(low[now],dfn[to]);
    }
    if(dfn[now]==low[now])
    {
        sccn++;//scc存的是每个点所在的强联通分量,sccn存数目
        while(true)
        {
            int fron=st.top();st.pop();
            cost[sccn]+=xx[fron];
            scc[fron]=sccn;
            if(fron==now) break;
        }
    }
}

无向图的割顶和桥:

给定一张无向图G=(V,E)。如果删除某个点u后,连通分量的数目增加,则称uG的割顶(cut vertex);如果删除某条边(u,v)后,连通分量的数目增加,则称(u,v)G的桥(bridge)。删除一个连通图中的割顶或桥,会使图不连通。

怎么求呢?
从一个节点开始做dfs,会形成一颗搜索树。与有向图中的搜索树不同。无向图中搜索树中各个子树之间不存在任何连边。
对于每次dfs的根节点,如果它有大于一个孩子,它一定是割顶。
对于其他每个节点u记录下它的dfn_ulow_u。如果点u存在一个孩子点v满足low[v]\geqslant dfn[u],即点v不能到达点u以上的祖先,把点u删去会使图的连通分量增加,从而点u是一个割顶。
对于一条边e_1=(u,v)如果uv的祖先,且low[v]>dfn[u],在没有重边e_2=(u,v)的情况下,e_1即是一座桥。

代码:

GD\to割点
GB\to割边

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=998244353;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,ans;
int head[N],cnt;
int vis[N],dfn[N],low[N],num;
struct Edge{int next,to;}edge[N*5];
inline void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
int GD[N],num_GD;
vector<P> GB; 
void dfs(int now,int fa)
{
    vis[now]=1;
    dfn[now]=low[now]=++num; int son=0;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;if(to==fa) continue;
        if(!vis[to]) 
        {
            dfs(to,now);
            low[now]=min(low[now],low[to]);
            if(low[to]>=dfn[now]) son++;
        }
        else low[now]=min(low[now],dfn[to]);
    }
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;if(to==fa) continue;
        if(low[to]>dfn[now]) 
            GB.push_back(P(min(to,now),max(to,now)));
    }
    if(son>=2||(son==1&&fa)) GD[++num_GD]=now;
}
void tarjan() {for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);}
signed main()
{
    read(n),read(m);
    for(int i=1,u,v;i<=m;i++) read(u),read(v),add(u,v),add(v,u);
    tarjan();
    sort(GD+1,GD+num_GD+1);
    for(int i=1;i<=num_GD;i++) printf("%d ",GD[i]); 
    if(num_GD==0) puts("Null"); else puts("");
    sort(GB.begin(),GB.end());
    int siz=GB.size();
    for(int i=0;i<siz;i++) printf("%d %d\n",GB[i].first,GB[i].second);
    return 0;
}

双联通分量:

给定一张无向连通图G=(V,E)。
如果删除任意点u后,图仍旧连通(或任意两点存在两条“点不重复”的路径),则称G是点-双连通的(一般简称双连通,biconnected);
如果删除某条边(u,v)后,图仍旧连通(或任意两点存在两条“边不重复”的路径),则称G是边-双连通的(edge-biconnected)。
G的极大点-双连通子图称为(点)双连通分量(Biconnected Component,BCC),或块(block)。
G的极大边-双连通子图称为边-双连通分量(edge-biconnected component)

无向图求点双:

桥不属于任何边-双联通分量,其他每条边恰好属于一个边-双连通分量。
删除所有的桥后,每个联通分量对应原图中的一个边-双联通分量。
将所有的边-双联通分量缩点后,得到的是一棵树。

边-双联通分量的求解非常简单。
先对G求出它所有的桥。断开所有的桥,求出它的所有连通分量。每个联通分量就是原图的一个双联通分量。

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=998244353;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,anss;
int head[N],cnt=1;
int vis[N],dfn[N],low[N],num;
int cant[N*5],ans[N];
struct Edge{int next,to;}edge[N*5];
inline void add(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
void dfs(int now,int fa)
{
    vis[now]=1;
    dfn[now]=low[now]=++num;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to; if(to==fa) continue;
        if(!vis[to]) dfs(to,now),low[now]=min(low[now],low[to]);
        else low[now]=min(low[now],dfn[to]);
    }
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to; if(to==fa) continue;
        if(low[to]>dfn[now]) cant[i]=cant[i^1]=1;
    }
}
void tarjan(){for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,i);}
void dfs_ans(int now,int zu)
{
    ans[now]=zu;
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(ans[to]||cant[i]) continue;
        dfs_ans(to,zu);
    }
}
int main()
{
    read(n),read(m);
    for(int i=1,u,v;i<=m;i++) read(u),read(v),add(u,v),add(v,u);
    tarjan();
    for(int i=1;i<=n;i++) if(!ans[i]) anss++,dfs_ans(i,i);
    printf("%d\n",anss);
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
    return 0;
}

无向图点双:

在割顶算法的基础上稍作改动就可以求解点-双连通分量.
和强连通算法一样维护一个栈。但由于割顶可以属于多个点-双连通分量,我们将边压入栈。
当存在low[v]>=dfn[u]即产生割顶时,我们将栈中的边取出,与这些边有关的点位于同一个点-双连通分量。
最好用vector记录一下每个点-双连通分量有哪些点,因为割顶记录的所处哪个连通分量的信息没有任何意义。


int vis[N], dfn[N], low[N], num; stack<Edge> st; int scc[N], sccn, new_sccn; void dfs(int now, int fa) { vis[now] = 1; dfn[now] = low[now] = ++num; for (int i = head[now]; i; i = edge[i].next) { int to = edge[i].to; if (!dfn[to]) { st.push(Edge{now, to}); dfs(to, now); low[now] = min(low[now], low[to]); if (low[to] >= dfn[now]) { node[++sccn].l = inf; vector<P> zz;zz.clear(); while (1) { Edge fron = st.top(); st.pop(); if (scc[fron.next] != sccn) { zz.push_back(P(fron.next,scc[fron.next])); scc[fron.next] = sccn; node[sccn].l = min(node[sccn].l, fron.next); node[sccn].r = max(node[sccn].r, fron.next); } if (scc[fron.to] != sccn) { zz.push_back(P(fron.to,scc[fron.to])); scc[fron.to] = sccn; node[sccn].l = min(node[sccn].l, fron.to); node[sccn].r = max(node[sccn].r, fron.to); } if (fron.next == now && fron.to == to) break; } if(zz.size()<=2) { node[sccn].l=inf,node[sccn].r=0,sccn--; int siz=zz.size(); for(int i=0;i<siz;i++) scc[zz[i].first]=zz[i].second; } } } else if (dfn[to] < dfn[now] && to != fa) { st.push(Edge{now, to}); low[now] = min(low[now], dfn[to]); } } } void tarjan() { for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, 0); }

参考:fyy神仙的课件…..

1 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注