Tarjan找桥和割点与点连通分量与边连通分量【未成形】

之前只学了个强连通Tarjan算法&＃xff0c;然后又摸了缩点操作&＃xff1b;

然后今天在lightoj摸了一道模板题&＃xff0c;是求所有桥的题&＃xff1b;

然后发现&＃xff0c;要把&＃xff1a;割点&＃xff0c;割点集合&＃xff0c;双连通&＃xff0c;最小割边集合&＃xff08;桥&＃xff09;&＃xff0c;点连通分量&＃xff0c;边连通分量都学一下。

--------------------

首先这个求割点是在无向图里面实现的&＃xff08;所以看到无向图有点感觉可以往这边考虑吧

先说割点&＃xff0c;割点集合&＃xff1a;

首先是割点这个问题啊&＃xff0c;就是说在一个连通图里面&＃xff0c;你删除某个点&＃43;这个点所连出去的边&＃xff0c;图变成了不连通&＃xff0c;就说这个点是割点&＃xff0c;

然后呢我再说这句话就好理解了&＃xff1a;在一个连通图中,如果有一个点集,删除这个点集&＃43;集合中所有点相关联的边,图变成了不连通&＃xff0c;就称这个点集为割点集合。

若在连通图上至少删去k个顶点才能破坏图的连通性&＃xff0c;则称此图的点连通度为k。

然后说桥&＃xff1b;

类似的&＃xff0c;如果一个边集&＃xff0c;删除这些边&＃xff08;注意是要求删去边集所有边以后&＃xff09;以后&＃xff0c;原图连通性被破坏&＃xff0c;就称这个点集为割边集合。

一个图的边连通度的定义为最小割边集合中的边数。

当且仅当这个图的边连通度是1&＃xff0c;则割边集合的唯一元素被称为桥&＃xff1b;

//以下摘自PKU的PDF和 bin神模板

求割点

看了别人的博客&＃xff1a;对啊&＃xff0c;首先就是暴力一点&＃xff0c;根据定义&＃xff0c;我遍历所有的点&＃xff0c;判断一下图是不是不连通了。

因为暴力所以优化啊。

在深度优先遍历整个图的过程中形成一棵搜索树&＃xff08;思路和有向图求强连通分量类似 &＃xff09;:

第一种方法&＃xff1a;

Dfn[u]定义和Tarjan算法一样&＃xff0c;表示编号为i的节点在DFS过程中 的访问序号(也可以叫做开始时间&＃xff09;。 

Low[u]定义为u或者u的子树中能够通过非父子边&＃xff08;父子边就是搜索树上的边&＃xff09;&＃xff0c;追溯到的最早的节点的DFS开始时间&＃xff1b;

一个顶点u是割点&＃xff0c;当且仅当满足(1)或(2)

(1)    是树根&＃xff08;其实这个根就一个&＃xff0c;就是最先进去的点&＃xff09;&＃xff0c;且u有多于一个子树。

(2)    u不为树根&＃xff0c;且存在(u,v)为树枝边&＃xff08;或称父子边&＃xff0c;即u为v在搜索树中的父亲&＃xff09;&＃xff0c;使得dfn(u)<&＃61;low[v];

我斌模板理解&＃xff1a;

const int N&＃61;1e4&＃43;10;
const int M&＃61;2e4&＃43;10;struct Edge{int to;int next;
};
Edge q[M*2];
int head[M*2],tol,n,m;
int dfn[N],low[N];
int ind,top;
bool flag[N],vis[N];void init()
{tol&＃61;0;memset(head,-1,sizeof(head));
}void add(int u,int v)
{q[tol].to&＃61;v;q[tol].next&＃61;head[u];head[u]&＃61;tol&＃43;&＃43;;
}void Tarjan(int u,int pre)
{int v;int son&＃61;0;low[u]&＃61;dfn[u]&＃61;ind&＃43;&＃43;;vis[u]&＃61;true;for(int i&＃61;head[u];i!&＃61;-1;i&＃61;q[i].next){v&＃61;q[i].to;if(v&＃61;&＃61;pre)continue;if(!dfn[v]){son&＃43;&＃43;;Tarjan(v,u);low[u]&＃61;min(low[v],low[u]);if(u!&＃61;pre&&low[v]>&＃61;dfn[u])//首先不是树根&＃xff0c;且存在(u,v)为树枝边。flag[u]&＃61;true;}elselow[u]&＃61;min(low[u],dfn[v]);}if(pre&＃61;&＃61;u&&son>1)//是树根&＃xff0c;且存在两棵子树flag[u]&＃61;true;
}void qiugedian()
{//各种初始化&＃xff1b;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(flag,0,sizeof(flag));ind&＃61;1;Tarjan(1,1); //我们随便设个1作为树根&＃xff0c;图上任意点都行&＃xff0c;无所谓&＃xff1b;int ans&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)if(flag[i])ans&＃43;&＃43;;
}


下面还是草稿、下次更新桥。。。。 

-------------------

第二种方法&＃xff1a;

也可以先用Tajan()进行dfs算出所有点的low和dfn值&＃xff0c;并记录dfs过程中每个点的父节点&＃xff0c;然后再把所有点看一遍&＃xff0c;看其low和dfn,以找出割点和桥。

找桥的时候&＃xff0c;要注意看有没有重边。有重边&＃xff0c;则不是桥。

const int MAXN &＃61; 10010;
const int MAXM &＃61; 100010;
struct Edge
{int to,next;bool cut; //是否为桥的标记
} edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;
void addedge(int u,int v)
{edge[tot].to &＃61; v;edge[tot].next &＃61; head[u];edge[tot].cut &＃61; false;head[u] &＃61; tot&＃43;&＃43;;
}void Tarjan(int u,int pre)
{int v;Low[u] &＃61; DFN[u] &＃61; &＃43;&＃43;Index;Stack[top&＃43;&＃43;] &＃61; u;Instack[u] &＃61; true; //入栈标记int son &＃61; 0; //对于节点u的for(int i &＃61; head[u]; i !&＃61; -1; i &＃61; edge[i].next){v &＃61; edge[i].to;if(v &＃61;&＃61; pre) //如果是他的父亲节点continue;if(!DFN[v]){son&＃43;&＃43;;Tarjan(v,u);if(Low[u] > Low[v]) Low[u] &＃61; Low[v];//桥//一条无向边(u,v)是桥&＃xff0c;当且仅当(u,v)为树枝边&＃xff0c;且满足DFN(u) DFN[u]){bridge&＃43;&＃43;;edge[i].cut &＃61; true;edge[i^1].cut &＃61; true;}//割点//一个顶点u是割点&＃xff0c;当且仅当满足(1)或(2) //(1) u为树根&＃xff0c;且u有多于一个子树//(2) u不为树根&＃xff0c;且满足存在(u,v)为树枝边(或称父子边&＃xff0c;即u为v在搜索树中的父亲)&＃xff0c;使得DFN(u)<&＃61;Low(v)if(u !&＃61; pre && Low[v] >&＃61; DFN[u])//不是树根{cut[u] &＃61; true;add_block[u]&＃43;&＃43;;}}else if( Low[u] > DFN[v])Low[u] &＃61; DFN[v];}//树根&＃xff0c;分支数大于1if(u &＃61;&＃61; pre && son > 1) cut[u] &＃61; true;if(u &＃61;&＃61; pre)add_block[u] &＃61; son - 1;Instack[u] &＃61; false;top--;
}