【专题复习】

**1. 最短路** 咕咕咕 **1. Tarjan** Tarjan家族——强联通 ``` int top,cnt,num,st[maxn],col[maxn],dfn[maxn],low[maxn],first[maxn],nxt[maxn]; void Tarjan(int u){ dfn[u]=low[u]=++num; st[++top]=u; for(int i=first[u];i;i=nxt[i]){ int v=to[i]; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else if(!co[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ co[u]=++col; while(st[top]!=u){ co[st[top]]=col; --top; } --top; } } ``` Tarjan 家族--边双 ``` int top,cnt,col_num,st[maxn],col[maxn],dfn[maxn],low[maxn]; void tarjan(int x,int fa) { dfn[x]=low[x]=++cnt; st[++top]=x; for(re int i=head[x];i;i=e[i].nxt) if(!dfn[e[i].v]) tarjan(e[i].v,x),low[x]=min(low[x],low[e[i].v]); else if(e[i].v!=fa) low[x]=min(low[x],dfn[e[i].v]); if(dfn[x]==low[x]) { col_num++; do { mid=st[top--]; col[mid]=col_num; }while(x!=mid); } } ``` tarjan 家族--点双 ``` int top,cnt,col_num,st[maxn],col[maxn],dfn[maxn],low[maxn]; int cut[maxn]; std::vector<int> bcc[maxn]; void tarjan(int x,int fa) { int sz=0; dfn[x]=low[x]=++cnt; for(re int i=head[x];i;i=e[i].nxt) if(!dfn[e[i].v]) { sz++,st[++top]=i; tarjan(e[i].v,x),low[x]=min(low[x],low[e[i].v]); if(low[e[i].v]>=dfn[x]) { cut[x]=1; col_num++; for(;;) { int k=st[top--]; if(col[e[k].u]!=col_num) col[e[k].u]=col_num,bcc[col_num].push_back(e[k].u); if(col[e[k].v]!=col_num) col[e[k].v]=col_num,bcc[col_num].push_back(e[k].v); if(k==i) break; } } } else if(e[i].v!=fa&&dfn[e[i].v]<low[x]) low[x]=dfn[e[i].v],st[++top]=i; if(!fa&&sz<2) cut[x]=0; } ``` 一些题目[草鉴定Grass Cownoisseur](https://www.luogu.org/problem/P3119) [校园网Network of Schools](https://www.luogu.org/problem/P2746)