LAC的tarjan(离线)算法---zoj_1141

????????? LCA就不解释了，这里主要再次复习一下LCA的tarjan的离线算法，所谓离线算法，就是把Q个查询先预存储起来，然后等预处理完成后，一次性处理Q个查询。相反所谓在线算法，即使输入一个查询就处理一个查询。今后会补上LCA的ST在线算法。

????? tarjan我非常崇拜，他解决了图论中很多问题，基本上都是基于DFS的，比如SCC,LCA等，那么tarjan离线如何运行呢，其中要配合并查集来实现。算法从根结点开始DFS，党遍历到某个节点时，为该节点创建一个集合，集合的先祖为该节点，当该节点的子节点被标记为黑时（即该节点的所有子节点都完成处理），子节点所对应的集合和该节点对应的集合合并，集合的先祖为该节点。次过程伴随着DFS进行。

????? DFS的过程其实也是查询的过程，当一个节点u被标记为黑，那么就在集合Q中找到查询(u,v)如果节点v也被标记为黑，那么LCA(u,v)就是节点v所在集合的先祖。

????? 下面分析一下复杂度，DPS为O(N)，并查集总共为N次合并操作,N次make-set操作和Q次寻找先祖操作共为a(N)*(N+Q),a(N)为一常数，对于每一个标记为黑的节点，找到对于的查询为O(1),公为O(N)，因此，整个tarjan操作为O(N+Q)。

????? 最后需要注意的是，tarjan在使用并查集union时，不能使用按秩合并。

zoj_1141

#include<iostream>#include<cstdio>#include<vector>#include<string.h>using namespace std;int n,m;int root[801];int visit[801];int res[801];class node{public:int value;vector<node*>v;};class query{public:vector<int>target;int total;query(){this->total=0;}};class union_find_set      {      public:          const static int maximum=801;       int anc;          int father[maximum];          int count[maximum];        int rank[maximum];                union_find_set()          {              for(int i=0;i<maximum;i++)              {                  this->father[i]=i;                  this->count[i]=1;           this->rank[i]=0;              }          }          int getFather(int v)          {              if(father[v]==v)              {                     return v;              }              else             {                  return  father[v]=getFather(father[v]);              }                 }          bool same(int x,int y)          {              return (getFather(x)==getFather(y));          }          bool judge(int x,int y)          {              int fx,fy;              fx=getFather(x);              fy=getFather(y);              if(fx==fy) return false;              else             {               /* if(rank[x]<rank[y])            {           father[fx]=fy;                      count[fy]+=count[fx];           }           else if(rank[x]>rank[y])           {           father[fy]=fx;               count[fx]+=count[fy];              }           else          {               father[fx]=fy;                      count[fy]+=count[fx];           ++rank[fy];           }  */father[fx]=fy; count[fy]+=count[fx];             return true;                  }                        }          void init()          {              for(int i=0;i<maximum;i++)              {                  this->father[i]=i;                  this->count[i]=1;             this->rank[i]=0;            }             }      };   vector<node*>l;union_find_set ufset;query qlist[801];void dfs(node*p){int size=p->v.size();for(int i=0;i<size;i++){dfs(p->v[i]);ufset.judge(p->v[i]->value,p->value);}visit[p->value]=1;int size2=qlist[p->value].total;for(int i=0;i<size2;i++){if(visit[qlist[p->value].target[i]]==1){int a=qlist[p->value].target[i];++res[ufset.getFather(a)];}}return;}int main(){freopen("e:\\zoj\\zoj_1141.txt","r",stdin);while(cin>>n){memset(root,0,sizeof(root));memset(visit,0,sizeof(visit));memset(res,0,sizeof(res));l.clear();ufset.init();for(int i=1;i<=n;i++){node*p=new node;p->value=i;l.push_back(p);}for(int j=1;j<=n;j++){int v,t;scanf("%d:(%d)",&v,&t);for(int i=1;i<=t;i++){int index;cin>>index;//scanf("%d",&index);root[index]=1;l[v-1]->v.push_back(l[index-1]);}}int q;cin>>q;//char c=getchar();memset(qlist,0,sizeof(qlist));int a,b;char c1,c2,c3;for(int i=1;i<=q;i++){//scanf("(%d,%d)",&a,&b);cin>>c1>>a>>c2>>b>>c3;if(a!=b){query qu;qlist[a].target.push_back(b);qlist[a].total++;qlist[b].target.push_back(a);qlist[b].total++;}else{query qu;qlist[a].target.push_back(b);qlist[a].total++;}}int r;for(int i=1;i<=n;i++){if(root[i]==0){r=i;break;}}dfs(l[r-1]);for(int i=1;i<=n;i++){if(res[i]!=0)cout<<i<<":"<<res[i]<<endl;}//cout<<r<<endl;}}

?