21 Sep 2016

双连通相关

说实话，学这玩意主要是想去A掉CodeChef May15 GRAPHCNT

当我学了一天顺便把POJ那道题A掉，感觉身体被掏空以后，回去看那题，惊奇的发现那道题是有向图

于是我的想法是这样的:

妈的智障

反正flag已经立下了，就来扯扯皮吧

一句写在前面的废话是双连通分量都是极大的。

首先是比较麻烦的割点和点双连通

这是一些关于割点的定义:

• 在无向连通图$G$上进行如下定义：

• 割点：若删掉某点$P$后，$G$分裂为两个或两个以上的子图，则称$P$为$G$的割点。

• 割点集合：在无向连通图$G$中，如果有一个顶点集合，删除这个顶点集合以及与该点集中的顶点相关联的边以后，原图分成多于一个连通块，则称这个点集为$G$的割点集合。　

• 点连通度：最小割点集合的大小称为无向图$G$的点连通度。

有关点连通度的自己理解错了，点联通度不可能为$0$哈，割点集合不是割点的集合哈，割点集合可以理解为一坨比较垃圾的点加起来发挥了割点的作用咋

如果里面有割点的话那么显然图$G$的连通度就是$1$

然后是关于点的双连通分量的定义:

• 点双连通图：点连通度大于1的图称为点双连通图（没有割点）。

这样定义有一个比较烦人的地方在于一个割点可能同属于许多点双连通分量，但没有办法。

求法的话大家都精通tarjan,随便放个垃圾的模板算了

Code(求割点)

void predfs(int v,const int &rt){
    pre[v]=lowlink[v]=++dfs_clock;
    int p=mark[v]=0;
    for(int i=0;i<G[v].size();++i){
        int to=G[v][i];
        if(pre[to])Min(lowlink[v],pre[to]);
        else{
            predfs(to,rt),Min(lowlink[v],lowlink[to]);
            mark[v]|=lowlink[to]>=pre[v];
            ++p;
        }
    }
    if(v==rt&&p<=1)mark[v]=0;
}

求割点要特判根这个路人皆知的东西我提一下

Code(求双连通分量)

inline void predfs(int v){
	pre[v]=lowlink[v]=++dfs_clock;
	stk[++tp]=v;
	for(int i=1;i<=n;++i){
		if(!G[v][i])continue;
		if(!pre[i]){
			predfs(i),Min(lowlink[v],lowlink[i]);
			if(lowlink[i]>=pre[v]){
				sub.clear();
				sub.pb(v);
				for(;tp;){
					int w=stk[tp--];
					sub.pb(w);
					if(w==i)break;
				}
				solve(sub);
			}
		}
		else Min(lowlink[v],pre[i]);
	}
}

那个$dfn$数组我习惯写成$pre$不要介意

$sub$是一个点的双连通分量，最后predfs完如果栈里还有元素的话也是一个双连通分量

其次是非常任性的桥和边双联通

类似的，先扯定义:

• 在无向连通图G上进行如下定义：

• 桥(割边)：若删掉某条边b后，G分裂为两个或两个以上的子图，则称B为G的桥(割边)。

• 割边集合：如果有一个边集合，删除这个边集以后，原图分成多于一个连通块，则称这个边集为割边集合。

• 边连通度：最小割边集合的大小称为无向图G的边连通度。

然后是有关边双联通的:

• 边双连通图：边连通度大于1的图称为边双连通图（没有割边）。

因为不会有点的重复，把桥找出来边的双连通分量也就出来了。

Code

inline void predfs(int v){
  	lowlink[v]=pre[v]=++dfs_clock;
    for(int i=head[v];~i;i=G[i].nxt){
      	int to=G[i].to;
      	if(!pre[to]){
          	predfs(to);
          	Min(lowlink[v],lowlink[to]);
          	if(lowlink[to]<pre[v])mark[i]=1;//这是桥咯
      	}
      	else Min(lowlink[v],pre[to]);
    }
}

我在Markdown上直接敲的，勿喷

Stats:

comments