柒葉灬 的博客

柒葉灬 的博客

图联通

posted on 2019-09-22 14:13:58 | under 专题总结 |

图联通


强联通分量

性质

  1. 强联通分量适用于有向图
  2. 强联通分量里面每一个点能互相到达
  3. 两个强联通分量有边当且仅当有两个有边的点分别在两个分量内
  4. 对于一个有向图做强联通缩点后可变为有向无环图
  5. 所以强联通缩点后可以拓扑排序

模板:

int top,stk[maxn];
bool instk[maxn];
int id,dfn[maxn],low[maxn];
int cnt,block[maxn];
void tarjan(int x){
    stk[++top]=x;
    dfn[x]=low[x]=++id;
    instk[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(instk[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[y]){
        cnt++;
        for(int y=-1;x!=y;){
        y=stk[top--];
            block[y]=cnt;
            instk[y]=0;
        }
    }
}

边双联通分量

桥(割边)

一个无向图中,如果删掉一条边,使得一个连通图变成两个图, 那么称这个边为桥

性质

  1. 边双联通分量适用于无向图
  2. 边双连通分量里面不存在桥
  3. 两个边双联通分量有边当且仅当两分量之间有桥
  4. 对于一个无向图做边双联通缩点后可变为树(森林)
  5. 所以边双联通缩点后可以用树上的算法

模板(与强联通基本一样)

void tarjan(int edge,int x){
//  注意不要走(edge^1)这个边
}

初始的时候 tot=1


点双连通分量

割点

一个无向图中,如果删掉一个点以及和他相连的边,使得一个连通图变成了多个子图,那么称这个点为割点

性质

  1. 点双联通分量适用于无向图
  2. 点双连通分量里面不存在割点
  3. 一点要注意 (1)---(2) 这是1个点双连通分量(两个节点一条边)
  4. 一个点可能属于多个点双连通分量
  5. 把所有点双连通分量和割点拉出来连边,会形成一颗树,且连通分量和割点是交互出现的

int id,dfn[maxn],low[maxn];
int block;
bool instk[maxn];
int top,stk[maxn];
vector<int>BCC[maxn],belong[maxn];
bool cut[maxn];
void tarjan(int f,int x){//根节点f=0
    belong[x].clear();
    dfn[x]=low[x]=++id;
    instk[x]=1;
    stk[++top]=x;
    for(int i=G.head[x];i;i=G.nxt[i]){
        int y=G.to[i];
        if(!dfn[y]){
            tarjan(x,y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                if(f)cut[x]=1;
                else f=-1;
                block++;
                BCC[block].clear();
                stk[++top]=x;
                for(int z=-1;z!=y;){
                    z=stk[top--];
                    BCC[block].push_back(z);
                    belong[z].push_back(block);
                }
            }
        }else if(y!=f)
            low[x]=min(low[x],dfn[y]);
    }
}

圆方树

有两种点:方点和圆点

方点就是原图中没有的

圆点就是原图中的点


目前我知道的圆方树有两种,

  1. 对于一个仙人掌来说(普通圆方树)
  2. 对于一个无向图点双缩点后的图来说(广义圆方树)

广义圆方树

可以直接用点双联通分量求,

一个点双连通分量可直接看成一个方点(可能要判大小是否为1)

方点与圆点连边就是每个点和它所在的点双联通分量连边。

普通圆方树

用第一种构造方法也可以,

但是可以扫到一个返祖边的时候,

把路径上所以的点直接建圆方点。

还有就是,如果发现了一个割点,就直接连边

这样子如果需要边权也方便