北大暑期学校图论1强连通分量

暑期课《ACM/ICPC竞赛训练信息学g procedure 3.第2步中产生的标记值相同的结点构成深度优先森林中深度优先搜索的复杂度:Θ(V计算GT的复杂度:0或者Θ(V+E)(临接表非常好的算法顶点数10,000,12.3.DAG上面如果有唯一的出度为0的点,则该点 POJ1236:Networkof ACM1236:ACM1236:Networkof顶点数1n0的点，m个出度为0 小。dfn值越小的节点，就称为越“早”。 DFS过程中，碰到哪个节点，就将哪个节点入如果发现某节点u有边连到栈里的节点v，则更新u的low值为min(low[u],dfn[v])，若low[u]被更新为dfn[v],则表明目前此时，显然栈中上方的节点，都是不能到达比u栈 出括,.有向图强连通分支的Tarjan有向图强连通分支的TarjanvoidTarjan(u){foreach(u,v)inEif(visnotvisted)low[u]=min(low[u],}elseif(vinstack)low[u]=min(low[u],}}ifdfn[ulow[u//u是一个强连通分量的根v=stack.popprintvuntil(u==}//退栈，把整个强连通分量都弹出}//复杂度是O(E+V)栈aabfcgdea栈bbafcgdeab

abcd

栈fcbcbae

abcd

栈fececbae

abcd

栈fg

cbcbae

abc

栈fdcdcba

de

abc

栈fdcdcba

de

abc

栈fdcdcba

de

abc

栈fg

{bcdaae

abc

fg

栈

{bcafdafe

abc

f

栈

{bce

d

gfa

abc

f

栈

{bce

d

gfa

abc

f

栈

{bc{afdedfn[u]=low[u],此时将栈中u及其上方的节点此时所有节点分成以下几类1）还没 过的节栈中比u早的节点(在u下方栈中比u晚的节点(在u上方曾经入栈 过），又出了栈的节要证明1)2)5)三类节点，都是要么从u不可达，要不可达u，且3)4）类节点互相可此时所有节点分成以下几类1）还没 栈中比u早的节(由u不可达，因为栈中比u晚的节点(由u可达栈中的曾经入栈 过），又出了栈的节点（不可达要证明第5)类节点不可达第3)类节点可达早于u晚于u面，u的下面---导致 定晚于u,x不可达u.由y可达,且y满足条件:最终的low[y]=dfn[y]。因为 证第5)类节点不可达 证第3)类节点可达若有此类节点x不可达u，则考虑最终的low[x]<low[x]=其他

）。而若low[y]=

b

g

cbd

e

一个顶点u是割点，当且仅当满足(1)或u为树根，且u有多于一 low[u]定义为u或者u的中能够通过if(v不是u的父节点)foreach(u,v)inE{if(visnotlow[u]=min(low[u],d[u]<low[v(uv)}else}}

if(v不是u的父节点low[u]=min(low[u],if(uisuuuu有一个子节点v，满足d[u}2445567

457#include<iostream>#include<vector>usingnamespacestd;#defineMyMax200typedefvector<int>Edge;boolVisited[MyMax];intdfn[MyMax];intlow[MyMax];intFather[MyMax];//DFS树中每个点的父节点boolbIsCutVetext[MyMax];//每个点是不是割点intnTime;//Dfs时间戳voidTarjan(intuintfather//father是u{Father[u]=father;inti,j,k;low[u]=dfn[u]=nTime++;for(i=0;i<G[u].size();i++){intv=if(!dfn[v])low[u]=}}

elseiffatherv//low[u]=void//intnRootSons=0;for(i=2;i<=n;i++)intv=Father[i];if(v==1)

intelse}}

if(dfn[v]<=bIsCutVetext[v]=if(nRootSons>bIsCutVetext[1]=true;for(i=1;i<=n;i++)cout<<i<<endl;for(i=1;i<=n;i++){intv=if(v>0&&dfn[v]<cout<<v<<","<<i}}int{intu,v;inti;nTime=cinnm//n是点数，m是边数for(i=1;i<=m;i++){cinuv;点编号从1开始}memset(dfn,0,sizeof(dfn));return}一个栈，当前双连通分支，在搜索图时树枝边（u,v)满足dfn(u)<=low(v)，说明u是aabgchdfebabagchdfeaabgchdfe

b

gc de

b

gc fe

b

gde

f

b

gde

f

b

g

{fc,ef,de,cdc de

b

g

{fc,ef,de,cdc d

{bce

f

b

g

{fc,ef,de,cdc d

{bce

f

b

g

{fc,ef,de,cdde

hf

{bc

b

g

{fc,ef,de,cdde

f

{bc

b

g

{fc,ef,de,cdde

f

{bc

b

g

{fc,ef,de,cdde

f

{bc244556711

BlockNo:BlockNo:BlockNo:BlockNo:BlockNo:Input:（8点9边81767

BlockNo:BlockNo:BlockNo:BlockNo:112345678#include<iostream>#include<vector>#include<queue>usingnamespacestd;#defineMyMax200typedefvector<int>Edge;vector<Edge>G(MyMax);intdfn[MyMax];intlow[MyMax];intnTime;intn,m;//n是点数，m是边数structEdge2{intu;intEdge2(intu_,intv_):u(u_),v(v_){intnBlockNo=0;voidTarjan(intu,int{intlow[u]=dfn[u]=nTime++;for(i=0;i<G[u].size();i++){intv=if(!dfn[v]){//v没 Edge2tmp(0,0);if(dfn[u]<=low[v])cout<<"BlockNo:"<<++<<do

tmp=Edges.back();Edges.pop_back();cout<<tmp.u<<","<<tmp.v<<}while(!(tmp.u==utmp.v==v)}}对应if(dfn[velseifvfather{//uif(dfn[u]>dfn[v])}}//对应for(i0;iG[u].size;i}int{intu,v;inti;nTime=c