Tarjan系列算法总结(hdu 1827,4612,4587,4005)
浏览数：43 /
时间：2015年06月08日
tarjan一直是我看了头大的问题，省选之前还是得好好系统的学习一下。我按照不同的算法在hdu上选题练习了一下，至少还是有了初步的认识。tarjan嘛，就是维护一个dfsnum[]和一个low[]，在dfs树上处理图的连通性等问题。细节处的不同导致算法本身的不同作用。
有向图强连通缩点：大体思路是维护一个栈，满足访问一个点就push到栈里面，当满足low[now]==dfn[now]时出栈，用dfn[]更新low[]当且仅当下一个点在栈内（注意不是递归栈）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 2200 #define MAXV MAXN #define MAXE MAXV*2 #define INF 0x3f3f3f3f struct Edge { int np; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; void addedge(int x,int y) { E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope]; } int status[MAXN]; int stack[MAXN],tops=-1; int low[MAXN],dfn[MAXN],dfstime; int top[MAXN]; void tarjan(int now) { status[now]=1; stack[++tops]=now; low[now]=dfn[now]=++dfstime; Edge *ne; for (ne=V[now];ne;ne=ne->next) { if (status[ne->np]==1) { low[now]=min(low[now],dfn[ne->np]); }else if (status[ne->np]==0) { tarjan(ne->np); low[now]=min(low[now],low[ne->np]); } } if (low[now]==dfn[now]) { while (stack[tops]!=now) { status[stack[tops]]=2; top[stack[tops--]]=now; } status[stack[tops]]=2; top[stack[tops--]]=now; } //status[now]=2; } int a[MAXN]; int el[MAXE][2]; int degi[MAXN]; int cirv[MAXN]; int main() { freopen("input.txt","r",stdin); int n,m,x,y,z; while (~scanf("%d%d",&n,&m)) { for (int i=1;i<=n;i++) scanf("%d",a+i); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); addedge(x,y); el[i][0]=x; el[i][1]=y; } for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i); for (int i=1;i<=m;i++) { if (top[el[i][0]]!=top[el[i][1]]) degi[top[el[i][1]]]++; } memset(cirv,INF,sizeof(cirv[0])*(n+10)); for (int i=1;i<=n;i++) cirv[top[i]]=min(cirv[top[i]],a[i]); int ans2=0,ans1=0; for (int i=1;i<=n;i++) { if (top[i]==i && !degi[top[i]]) { ans1++; ans2+=cirv[top[i]]; } } printf("%d %d\n",ans1,ans2); memset(V,0,sizeof(V[0])*(n+10)); memset(dfn,0,sizeof(dfn[0])*(n+10)); memset(degi,0,sizeof(degi[0])*(n+10)); memset(status,0,sizeof(status[0])*(n+10)); tope=-1; dfstime=0; } }
无向图求桥边：这种类型算是最简单的把，唯一要注意的是要记录每个“编号”的边是否访问，而不是点。
这道题我认认真真写的非递归tarjan，参考集训某些大神的非递归，让我领会到了非递归的“精髓”，以后再也不用类似于记录当前运行到什么语句的方法了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 210000 #define MAXV MAXN #define MAXE 1100000*2 #define INF 0x3f3f3f3f struct Edge { int np; int id; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; void addedge(int x,int y,int id=0) { E[++tope].np=y; E[tope].next=V[x]; E[tope].id=id; V[x]=&E[tope]; } int status[MAXN]; int low[MAXN],dfn[MAXN],dfstime; bool is_bridge[MAXE]; bool edge_vis[MAXE]; void tarjan(int now) { Edge *ne; status[now]=1; low[now]=dfn[now]=++dfstime; for (ne=V[now];ne;ne=ne->next) { if (edge_vis[ne->id])continue; if (status[ne->np]==1) { low[now]=min(low[now],dfn[ne->np]); }else if (status[ne->np]==0) { edge_vis[ne->id]=true; tarjan(ne->np); low[now]=min(low[now],low[ne->np]); if (low[ne->np]==dfn[ne->np]) is_bridge[ne->id]=true; } } } int tarj_now[MAXN],tarj_step[MAXN]; Edge *tarj_ne[MAXN]; int lev=-1; #define ne tarj_ne[cur] #define now tarj_now[cur] void tarjan2(int root) { int cur=0; now=root; ne=V[root]; status[now]=1; low[now]=dfn[now]=++dfstime; while (true) { tarj_begin: if (ne) { if (!edge_vis[ne->id]) { if (status[ne->np]==1) low[now]=min(low[now],dfn[ne->np]); else if (status[ne->np]==0) { edge_vis[ne->id]=true; tarj_now[cur+1]=ne->np; tarj_ne[cur+1]=V[tarj_now[cur+1]]; cur++; status[now]=true; low[now]=dfn[now]=++dfstime; goto tarj_begin; tarj_back: low[now]=min(low[now],low[ne->np]); if (low[ne->np]==dfn[ne->np]) is_bridge[ne->id]=true; } } ne=ne->next; }else { cur--; if (cur==-1)break; goto tarj_back; } } } #undef now #undef ne int el[MAXE][2]; int uf[MAXN]; int rk[MAXN]; int get_fa(int now) { return now==uf[now] ? now : uf[now]=get_fa(uf[now]) ; } void comb(int x,int y) { x=get_fa(x); y=get_fa(y); if (rk[x]>rk[y]) { uf[y]=x; rk[x]=max(rk[x],rk[y]+1); }else { uf[x]=y; rk[y]=max(rk[y],rk[x]+1); } } int dis[MAXN]; int q[MAXN]; int pnt[MAXN]; int bfs(int now) { int head=-1,tail=0; Edge *ne; q[0]=now; dis[now]=0; pnt[now]=now; int res=now; while (head<tail) { now=q[++head]; if (dis[res]<dis[now])res=now; for (ne=V[now];ne;ne=ne->next) { if (ne->np==pnt[now])continue; q[++tail]=ne->np; dis[ne->np]=dis[now]+1; pnt[ne->np]=now; } } return res; } int main() { freopen("input.txt","r",stdin); int n,m,x,y,z; while (scanf("%d%d",&n,&m),n+m) { memset(V,0,sizeof(V)); tope=-1; dfstime=0; memset(status,0,sizeof(status)); memset(is_bridge,0,sizeof(is_bridge)); memset(edge_vis,0,sizeof(edge_vis)); memset(dfn,0,sizeof(dfn)); int tot=0; for (int i=1;i<=n;i++) uf[i]=i,rk[i]=1; for (int i=0;i<m;i++) { scanf("%d%d",&x,&y); addedge(x,y,i); addedge(y,x,i); el[i][0]=x; el[i][1]=y; } for (int i=1;i<=n;i++) if (!dfn[i]) tarjan2(i); for (int i=0;i<m;i++) { if (is_bridge[i]) tot++; else comb(el[i][0],el[i][1]); } for (int i=1;i<=n;i++) uf[i]=get_fa(i); memset(V,0,sizeof(V)); tope=-1; for (int i=0;i<m;i++) { if (get_fa(el[i][0])==get_fa(el[i][1]))continue; addedge(get_fa(el[i][0]),get_fa(el[i][1])); addedge(get_fa(el[i][1]),get_fa(el[i][0])); } x=1; x=bfs(get_fa(x)); x=bfs(x); printf("%d\n",tot-dis[x]); } }
无向图求割点：这种类型很容易想错，而且也很难调试，首先我们需要对dfs的根节点分类讨论，其次，如果一个点有不止一次满足向下调用low[to]>=dfn[now]或不存在low[to]<=low[pnt]，则这个点是割点。
顺便吐槽一下，网上粘的标程没有一个靠谱的，真不知道数据要水成啥样才能把它们放过。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 5500 #define MAXE MAXN*2 #define INF 0x3f3f3f3f #define MAXV MAXN struct Edge { int np,id; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; void addedge(int x,int y,int id) { E[++tope].np=y; E[tope].id=id; E[tope].next=V[x]; V[x]=&E[tope]; } bool edge_vis[MAXE]; int low[MAXN],dfn[MAXN]; int dfstime=0; int root; int ans; bool cut_p[MAXN]; int status[MAXN]; void tarjan(int now,int p) { int totd=0; dfn[now]=low[now]=++dfstime; Edge *ne; for (ne=V[now];ne;ne=ne->next) { if (ne->np==p)continue; if (!dfn[ne->np]) { tarjan(ne->np,now); if (low[ne->np]>=dfn[now]) totd++; low[now]=min(low[now],low[ne->np]); }else { low[now]=min(low[now],dfn[ne->np]); } } ans=max(ans,(totd+(now!=root))-1); } int el[MAXE][2]; int main() { freopen("input.txt","r",stdin); int x,y,z,n,m; while (~scanf("%d %d\n",&n,&m)) { for (int i=0;i<m;i++) { scanf("%d%d",&x,&y); x++;y++; el[i][0]=x; el[i][1]=y; } int res=0; int tot; for (int i=1;i<=n;i++) { ans=-INF; tot=0; memset(V,0,sizeof(V)); tope=-1; dfstime=0; memset(dfn,0,sizeof(dfn)); for (int j=0;j<m;j++) if (el[j][0]!=i && el[j][1]!=i) addedge(el[j][0],el[j][1],j), addedge(el[j][1],el[j][0],j); for (int j=1;j<=n;j++) { if (j==i)continue; if (!dfn[j]) { tot++; root=j; tarjan(j,j); } } res=max(res,tot+ans); } printf("%d\n",res); } }
点双连通分量：同求桥边。网上都说这是边双，根本搞不清楚。这道题主要是细节坑人，其他都没什么。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define MAXN 10100 #define MAXV MAXN #define MAXE MAXN*20 #define INF 0x3f3f3f3f struct Edge { int np,id,val; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; void addedge(int x,int y,int z,int id) { E[++tope].np=y; E[tope].val=z; E[tope].id=id; E[tope].next=V[x]; V[x]=&E[tope]; } int dfn[MAXN],low[MAXN],top[MAXN],dfstime; bool edge_vis[MAXE]; int stack[MAXN],tops=-1; vector<int> bridge; void tarjan(int now) { Edge *ne; low[now]=dfn[now]=++dfstime; stack[++tops]=now; for (ne=V[now];ne;ne=ne->next) { if (edge_vis[ne->id])continue; edge_vis[ne->id]=true; if (dfn[ne->np]) { low[now]=min(low[now],dfn[ne->np]); }else { tarjan(ne->np); low[now]=min(low[now],low[ne->np]); if (low[ne->np]==dfn[ne->np]) { while (stack[tops]!=ne->np) top[stack[tops--]]=ne->np; top[stack[tops--]]=ne->np; bridge.push_back(ne->id); } } } } struct edge { int x,y,z,id; }el[MAXE],eb[MAXE]; bool cmp_z(edge e1,edge e2) { return e1.z<e2.z; } int q[MAXN]; int pnt[MAXN]; int depth[MAXN]; void bfs(int now) { int head=-1,tail=0; Edge *ne; q[0]=now; pnt[now]=now; depth[now]=1; while (head<tail) { now=q[++head]; for (ne=V[now];ne;ne=ne->next) { if (ne->np==pnt[now])continue; q[++tail]=ne->np; depth[ne->np]=depth[now]+1; pnt[ne->np]=now; } } return ; } int jump[20][MAXN]; void init_lca(int n) { for (int i=1;i<=n;i++) jump[0][i]=pnt[i]; for (int j=1;j<20;j++) for (int i=1;i<=n;i++) jump[j][i]=jump[j-1][jump[j-1][i]]; } int lca(int x,int y) { if (depth[x]<depth[y]) swap(x,y); int dep=depth[x]-depth[y]; for (int i=0;i<20;i++) if (dep&(1<<i)) x=jump[i][x]; if (x==y)return x; for (int i=19;i>=0;i--) if (jump[i][x]!=jump[i][y]) x=jump[i][x],y=jump[i][y]; return pnt[x]; } int main() { freopen("input.txt","r",stdin); int n,m; int x,y,z; while (~scanf("%d%d",&n,&m)) { memset(V,0,sizeof(V)); memset(dfn,0,sizeof(dfn)); tope=-1; bridge.clear(); memset(pnt,0,sizeof(pnt)); memset(edge_vis,0,sizeof(edge_vis)); dfstime=0; for (int i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); el[i].x=x; el[i].y=y; el[i].z=z; el[i].id=i; addedge(x,y,z,i); addedge(y,x,z,i); } for (int i=1;i<=n;i++) { if (!dfn[i]) { tarjan(i); while (~tops) top[stack[tops--]]=i; } } memset(V,0,sizeof(V)); tope=-1; int l=bridge.size(); for (int i=0;i<bridge.size();i++) { eb[i]=el[bridge[i]]; eb[i].x=top[eb[i].x]; eb[i].y=top[eb[i].y]; addedge(eb[i].x,eb[i].y,0,0); addedge(eb[i].y,eb[i].x,0,0); } bfs(top[1]); init_lca(n); sort(eb,eb+l,cmp_z); int l2,l1,hh; int a; l1=eb[0].x,hh=eb[0].y; l2=-1; if (depth[l1]<depth[hh])swap(l1,hh); int res=-1; for (int i=1;i<l;i++) { for (int j=0;j<2;j++) { a=j?eb[i].y:eb[i].x; if (lca(a,l1)==l1) { l1=a; }else if (~l2 && lca(a,l2)==l2) { l2=a; }else if (~l2 && lca(a,l2)==a && lca(a,hh)==hh) { //okay }else if (lca(a,l1)==a && lca(a,hh)==hh) { //okay }else if (lca(a,hh)==a && l2==-1) { hh=a; }else if (depth[lca(a,l1)]<=depth[hh] && l2==-1) { l2=a; hh=lca(a,l1); }else { res=eb[i].z; break; } } if (~res)break; } printf("%d\n",res); } }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
