首页 > 代码库 > Tarjan算法各种&RMQ& POJ 3694
Tarjan算法各种&RMQ& POJ 3694
关于tarjan 的思想可以在网上搜到，具体我也不太清楚，应该说自己理解也不深，下面是做题经验得到的一些模板。
其中有很多转载，包括BYVoid等，感谢让我转。。。望各路大神愿谅
有向图求连通分量的一般方法：
1 void Tarjan(u) { 2 dfn[u]=low[u]=++index 3 stack.push(u) 4 for each (u, v) in E { 5 if (v is not visted) { 6 tarjan(v) 7 low[u] = min(low[u], low[v]) 8 } 9 else if (v in stack) { //可设置stack数组 10 low[u] = min(low[u], dfn[v]) 11 } 12 } 13 if (dfn[u] == low[u]) { //u是一个强连通分量的根 14 repeat 15 v = stack.pop 16 print v 17 until (u== v) 18 } //退栈，把整个强连通分量都弹出来 19 //此时可为所弹出的联通分量标号，便于0重建图 20 } //复杂度是O(E+V)的
无相连通图割点满足条件 （ 重边对割点不影响 ，这很重要）
一个顶点u是割点，当且仅当满足(1)或(2)
(1) u为树根，且u有多于一个子树。
(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，即u为v在搜索树中的父亲)，使得dfn(u)<=low(v)。
1 void tarjan(int x){ 2 v[x]=1; 3 dfn[x]=low[x]=++num; 4 for(int i=head[x];i;i=next[i]) 5 if(!v[ver[i]]){ 6 tarjan(ver[i]); 7 low[x]=min(low[x],low[ver[i]]); 8 if(dfn[x]<=low[ver[i]]) 9 v[x]++; 10 } 11 else 12 low[x]=min(low[x],dfn[ver[i]]); 13 if((x==root&&v[x]>2)||(x!=root&&v[x]>1)) 14 v[x]=2; 15 else 16 v[x]=1;//v[x]=2表示该点为割点，注意其中第一个点要特判 17 }
无相连通图（可能存在重边的情况下）桥
1 void tarjan(int u){ 2 dfn[u]=low[u]=++clock; 3 for(int e=head[u];e!=-1;e=edge[e].next){ 4 int v=edge[e].v; 5 if(dfn[v]==-1){ 6 vis_e[e]=vis_e[e^1]=true; 7 tarjan(v); 8 low[u]=min(low[u],low[v]); 9 if(dfn[u] >=low[v]){ 10 // Union(u,v); 两点在同一个分量中，合并可得边双连通图 11 } 12 else{ 13 is_bridge[e] = is_bridge[e^1] = true; 14 } 15 } 16 else if(dfn[v] < dfn[u] && !vis_e[e]){ 17 vis_e[e] = vis_e[e^1] = true; 18 low[u]=min(low[u],dfn[v]); 19 } 20 } 21 }
把求桥和求割点合并在一个程序中（不考虑重边）
1 void Tarjan(int u, int father){ //father 是u的父节点 2 Father[u] = father; 3 int i,j,k; 4 low[u] = dfn[u] = nTime ++; 5 for( i = 0;i < G[u].size() ;i ++ ) { 6 int v = G[u][i]; 7 if( ! dfn[v]) { 8 Tarjan(v,u); 9 low[u] = min(low[u],low[v]); 10 } 11 else if( father != v ) //连到父节点的回边不考虑，否则求不出桥 12 low[u] = min(low[u],dfn[v]); 13 } 14 } 15 void Count(){ //计算割点和桥 16 int nRootSons = 0; int i; 17 Tarjan(1,0); 18 for( i = 2;i <= n;i ++ ) { 19 int v = Father[i]; 20 if( v == 1 ) 21 nRootSons ++; //DFS树中根节点有几个子树 22 else { 23 if( dfn[v] <= low[i]) //判断割点条件 24 bIsCutVetext[v] = true; 25 } 26 } 27 if( nRootSons > 1) //根结点至少有两个子树 28 bIsCutVetext[1] = true; 29 for( i = 1;i <= n;i ++ ) 30 if( bIsCutVetext[i] ) //割点 31 cout << i << endl; 32 for( i = 1;i <= n;i ++) { 33 int v = Father[i]; 34 if(v >0 && dfn[v] < low[i]) // 割边 35 cout << v << "," << i <<endl; 36 } 37 }
求点双连通实际上是在求割点时得到的。
对于点双连通分支，实际上在求割点的过程中就能顺便把每个点双连通分支求出。建立一个栈，存储当前双连通分支，在搜索图时，每找到一条树枝边或反向边，就把这条边加入栈中。如果遇到某时满足dfn(u)<=low(v)，说明u是一个割点，同时把边从栈顶一个个取出，直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分支。割点可以属于多个点双连通分支，其余点和每条边只属于且属于一个点双连通分支。
1 void Tarjan(int u, int father){ 2 int i,j,k; 3 low[u] = dfn[u] = nTime ++; 4 for( i = 0;i < G[u].size() ;i ++ ) { 5 int v = G[u][i]; 6 if( ! dfn[v]) { //v没有访问过 7 //树边要入栈 8 Edges.push_back(Edge2(u,v)); 9 Tarjan(v,u); 10 low[u] = min(low[u],low[v]); 11 Edge2 tmp(0,0); 12 if(dfn[u] <= low[v]) { 13 //从一条边往下走，走完后发现自己是割点，则栈中的边一定全是和自己在一个双连通分量里面 14 //根节点总是和其下的某些点在同一个双连通分量里面 15 cout << "Block No: " << ++ nBlockNo << endl; 16 do { 17 tmp = Edges.back(); 18 Edges.pop_back (); 19 cout << tmp.u << "," << tmp.v << endl; 20 }while ( !(tmp.u == u && tmp.v == v) ); 21 } 22 } // 对应if( ! dfn[v]) { 23 else { 24 if( v != father ) {//u连到父节点的回边不考虑 25 low[u] = min(low[u],dfn[v]); 26 if( dfn[u] > dfn[v]) 27 //子孙连接到祖先的回边要入栈，但是子孙连接到自己的边，此处肯定已经入过栈了，不能再入栈 28 Edges.push_back(Edge2(u,v)); 29 } 30 } 31 } //对应 for( i = 0;i < G[u].size() ;i ++ ) { 32 }
一个有桥的连通图，如何把它通过加边变成边双连通图？
方法为首先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。
统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。则至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
LCA问题
LCA
Tarjan作为离线off-line算法，在程序开始前，需要将所有等待询问的节点对提前存储，然后程序从树根开始执行TarjanLCA()。假如有如下一棵多叉树
根据TarjanLCA的实现算法可以看出，只有当某一棵子树全部遍历处理完成后，才将该子树的根节点标记为黑色（初始化是白色），假设程序按上面的树形结构进行遍历，首先从节点1开始，然后递归处理根为2的子树，当子树2处理完毕后，节点2， 5， 6均为黑色；接着要回溯处理3子树，首先被染黑的是节点7（因为节点7作为叶子不用深搜，直接处理），接着节点7就会查看所有询问(7, x)的节点对，假如存在(7, 5)，因为节点5已经被染黑，所以就可以断定(7, 5)的最近公共祖先就是find(5).ancestor，即节点1（因为2子树处理完毕后，子树2和节点1进行了union，find(5)返回了合并后的树的根1，此时树根的ancestor的值就是1）。 有人会问如果没有(7, 5)，而是有(5, 7)询问对怎么处理呢？我们可以在程序初始化的时候做个技巧，将询问对(a, b)和(b, a)全部存储，这样就能保证完整性。
1 function TarjanLCA(u) 2 MakeSet(u); 3 u.ancestor := u; 4 for each v in u.children do 5 TarjanLCA(v); 6 Union(u,v); 7 Find(v).ancestor := u; //把v的父亲置为u 8 u.colour := black; 9 for each v such that {u,v} in P do // P 存储所有等待询问的节点对 10 if v.colour == black 11 print "Tarjan‘s Least Common Ancestor of " + u + 12 " and " + v + " is " + Find(v).ancestor + "." //此处一定是v
RMQ
LCA向RMQ转化
对有根树T进行DFS，将遍历到的结点按照顺序记下，我们将得到一个长度为2N – 1的序列，称之为T的欧拉序列F
每个结点都在欧拉序列中出现，我们记录结点u在欧拉序列中第一次出现的位置为pos(u)
此处要先介绍人ST算法：
ST算法是使用预处理来获得效率的。
预处理:
预处理使用DP的思想，f(i, j)表示[i, i+2^j - 1]区间中的最小值，我们可以开辟一个数组专门来保存f(i, j)的值。
例如，f(0, 0)表示[0,0]之间的最小值,就是num[0], f(0, 2)表示[0, 3]之间的最小值, f(2, 4)表示[2, 17]之间的最小值
注意, 因为f(i, j)可以由f(i, j - 1)和f(i+2^(j-1), j-1)导出, 而递推的初值(所有的f(i, 0) = i)都是已知的
所以我们可以采用自底向上的算法递推地给出所有符合条件的f(i, j)的值。
查询:
假设要查询从m到n这一段的最小值, 那么我们先求出一个最大的k, 使得k满足2^k <= (n - m + 1).
于是我们就可以把[m, n]分成两个(部分重叠的)长度为2^k的区间: [m, m+2^k-1], [n-2^k+1, n];
而我们之前已经求出了f(m, k)为[m, m+2^k-1]的最小值, f(n-2^k+1, k)为[n-2^k+1, n]的最小值
我们只要返回其中更小的那个, 就是我们想要的答案, 这个算法的时间复杂度是O(1)的.
例如, rmq(0, 11) = min(f(0, 3), f(4, 3))
1 void st(int n){ 2 int i, j, k, m; 3 k = (int) (log((double)n) / log(2.0)); 4 for(i = 0; i < n; i++) { 5 f1[i][0] = num[i]; //递推的初值 6 f2[i][0] = num[i]; 7 } 8 for(j = 1; j <= k; j++) { //自底向上递推 9 for(i = 0; i + (1 << j) - 1 < n; i++) { 10 m = i + (1 << (j - 1)); //求出中间的那个值 11 f1[i][j] = mmax(f1[i][j-1], f1[m][j-1]); 12 f2[i][j] = mmin(f2[i][j-1], f2[m][j-1]); 13 } 14 } 15 }
查询
1 void rmq(int i, int j) { 2 int k = (int)(log(double(j-i+1)) / log(2.0)), t1, t2; //用对2去对数的方法求出k 3 t1 = mmax(f1[i][k], f1[j - (1<<k) + 1][k]); 4 t2 = mmin(f2[i][k], f2[j - (1<<k) + 1][k]); 5 printf("%d\n",t1 - t2); 6 }
LCA转RMQ中
则LCA中求最近公共祖先就是在最先出现的位置区间内求
求该深度序列深度最小值所对应的欧拉序列的点
//这个算法是利用了RMQ的思想，DP记录的是某段区间最小值的位置
1 void st(){ 2 int i, j, k, m; 3 for(i=1;i<=time;i++) 4 dp[i][0]=i; 5 for(j=1;(1<<j)<=time;j++) 6 { 7 for(i=1;i+(1<<j)-1<=time;i++) 8 { 9 if(depth[dp[i][j-1]]<depth[dp[i+(1<<(j-1))][j-1]]) 10 dp[i][j]=dp[i][j-1]; 11 else 12 dp[i][j]=dp[i+(1<<(j-1))][j-1]; 13 } 14 } 15 } 16 //depth是深度序列 17 int rmq(int i, int j) { 18 int k = (int)(log(double(j-i+1)) / log(2.0)); 19 return k; 20 } 21 //squ是欧拉序列 22 int find(int s,int x){ 23 int t1=first[s],t2=first[x]; // first是首次出现的位置 24 if(t1>t2){ 25 int tmp=t1; 26 t1=t2; 27 t2=tmp; 28 } 29 int t=rmq(t1,t2); int ancestor; 30 if(depth[dp[t1][t]]<depth[dp[t2-(1<<t)+1][t]]) 31 ancestor=squ[dp[t1][t]]; 32 else 33 ancestor=squ[dp[t2-(1<<t)+1][t]]; 34 return ancestor; 35 }
POJ 3694
求出所有的桥后缩点，则变成树。树的每一条边均为桥。
那么，要求增加一条边后还剩多少条桥，可知，两点到其LCA的路径均不成为桥。
但此处求LCA时有一个小技巧，因为要统计数目。所以，可能通过减少深度的操作完成。先把两点提至同一深度，然后再两点同时向根回溯，每经过边则减少一条桥。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int MAXN=100010; 5 const int MAXM=200100; 6 7 struct { 8 int u,v; 9 int next; 10 }edge[MAXM*2],tree[MAXM*2]; 11 int tot,n,m,clock,k; 12 int head[MAXN],dfn[MAXN],low[MAXN],pre[MAXN],rank[MAXN]; 13 bool vis_e[MAXM*2],is_bridge[MAXM*2],visT[MAXN]; 14 int depth[MAXN],p[MAXN],head_T[MAXN]; 15 void addedge(int u,int v){ 16 vis_e[tot]=is_bridge[tot]=false; 17 edge[tot].u=u; 18 edge[tot].v=v; 19 edge[tot].next=head[u]; 20 head[u]=tot++; 21 vis_e[tot]=is_bridge[tot]=false; 22 edge[tot].u=v; 23 edge[tot].v=u; 24 edge[tot].next=head[v]; 25 head[v]=tot++; 26 } 27 28 void addTree(int u,int v){ 29 //vis_e[tot]=false; 30 tree[tot].u=u; 31 tree[tot].v=v; 32 tree[tot].next=head_T[u]; 33 head_T[u]=tot++; 34 // vis_e[tot]=false; 35 tree[tot].u=v; 36 tree[tot].v=u; 37 tree[tot].next=head_T[v]; 38 head_T[v]=tot++; 39 } 40 41 int find(int x){ 42 int r=x; 43 while(pre[r]!=-1) 44 r=pre[r]; 45 while(pre[x]!=-1){ 46 int tx=pre[x]; 47 pre[x]=r; 48 x=tx; 49 } 50 return r; 51 } 52 int min(int a,int b){ 53 if(a<b)return a; 54 return b; 55 } 56 57 void Union(int x,int y){ 58 int xx=find(x); 59 int yy=find(y); 60 if(rank[xx]>rank[yy]) 61 pre[yy]=xx; 62 else if(rank[xx]<rank[yy]) 63 pre[xx]=yy; 64 else { 65 pre[xx]=yy; 66 rank[yy]++; 67 } 68 } 69 70 void tarjan(int u){ 71 dfn[u]=low[u]=++clock; 72 for(int e=head[u];e!=-1;e=edge[e].next){ 73 int v=edge[e].v; 74 if(dfn[v]==-1){ 75 vis_e[e]=vis_e[e^1]=true; 76 tarjan(v); 77 low[u]=min(low[u],low[v]); 78 if(dfn[u] >=low[v]){ 79 // cout<<u<<‘ ‘<<v<<endl; 80 Union(u,v); 81 } 82 else{ 83 is_bridge[e] = is_bridge[e^1] = true; 84 // cout<<u<<‘ ‘<<v<<endl; 85 } 86 } 87 else if(dfn[v] < dfn[u] && !vis_e[e]){ 88 vis_e[e] = vis_e[e^1] = true; 89 low[u]=min(low[u],dfn[v]); 90 } 91 } 92 } 93 94 int count; 95 void dfs(int r,int c){ 96 int i,j,u,v; 97 depth[r]=c; 98 visT[r]=true; 99 count++; 100 for(i=head_T[r];i!=-1;i=tree[i].next){ 101 v=tree[i].v; 102 //cout<<v<<endl; 103 if(!visT[v]){ 104 // cout<<v<<endl; 105 p[v]=r; 106 dfs(v,c+1); 107 } 108 } 109 visT[r]=false; 110 } 111 112 void lca(int x,int y){ 113 if(depth[x]>depth[y]){ 114 while(depth[x]!=depth[y]){ 115 if(!visT[x]){ 116 visT[x]=true; 117 count--; 118 } 119 x=p[x]; 120 } 121 } 122 if(depth[x]<depth[y]){ 123 while(depth[x]!=depth[y]){ 124 if(!visT[y]){ 125 visT[y]=true; 126 count--; 127 } 128 y=p[y]; 129 } 130 } 131 if(depth[x]==depth[y]){ 132 while(x!=y){ 133 if(!visT[x]){ 134 visT[x]=true; 135 count--; 136 } 137 x=p[x]; 138 if(!visT[y]){ 139 visT[y]=true; 140 count--; 141 } 142 y=p[y]; 143 } 144 } 145 } 146 147 int main(){ 148 int u,v,j,i; int tt=0; 149 while(scanf("%d%d",&n,&m)!=EOF){ 150 tt++; 151 if(!n&&!m) break; 152 for(i=1;i<=n;i++){ 153 head[i]=pre[i]=head_T[i]=-1; 154 dfn[i]=low[i]=-1; 155 rank[i]=0; 156 p[i]=-1; 157 } 158 tot=0; clock=0; 159 for(i=1;i<=m;i++){ 160 scanf("%d%d",&u,&v); 161 addedge(u,v); 162 } 163 tarjan(1); 164 // cout<<"YES"<<endl; 165 // system("pause"); 166 tot=0; 167 int root; 168 for(i=1;i<=n;i++){ 169 visT[i]=false; 170 for(j=head[i];j!=-1;j=edge[j].next){ 171 v=edge[j].v; 172 if(is_bridge[j]){ 173 int x=find(i); 174 int y=find(v); 175 // cout<<x<<‘ ‘<<y<<endl; 176 root=x; 177 addTree(x,y); 178 is_bridge[j]=is_bridge[j^1]=false; 179 } 180 } 181 } 182 // cout<<"YES"<<endl; 183 count=0; 184 dfs(root,0); count--; 185 // cout<<"YES"<<endl; 186 scanf("%d",&k); 187 printf("Case %d:\n",tt); 188 while(k--){ 189 scanf("%d%d",&u,&v); 190 int x=find(u); 191 int y=find(v); 192 if(x==y||(visT[x]&&visT[y])) 193 printf("%d\n",count); 194 else{ 195 lca(x,y); 196 printf("%d\n",count); 197 } 198 } 199 printf("\n"); 200 } 201 return 0; 202 }