POJ 1470 LCA tarjan 离线算法 - c++编程基础

TOP

POJ 1470 LCA tarjan 离线算法

2015-07-20 17:25:33 来源: 作者: 【大中小】浏览:2次

这里有个讲解非常明白，虽然没证明。点击打开链接还有个数据结构的学习点击打开链接伸展树/Treap/划分树/ 归并树

步骤：

tarjan算法的步骤是(当dfs到节点u时):
1 在并查集中建立仅有u的集合,设置该集合的祖先为u
1 对u的每个孩子v:
1.1 tarjan之
1.2 合并v到父节点u的集合,确保集合的祖先是u
2 设置u为已遍历
3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; /* * POJ 1470 * 给出一颗有向树，Q个查询 * 输出查询结果中每个点出现次数 */ /* * LCA离线算法，Tarjan * 复杂度O(n+Q); */ const int MAXN = 1010; const int MAXQ = 500010;//查询数的最大值 //并查集部分 int F[MAXN];//需要初始化为-1 int find(int x) { if(F[x] == -1)return x; return F[x] = find(F[x]); } void bing(int u,int v) { int t1 = find(u); int t2 = find(v); if(t1 != t2) F[t1] = t2; } //************************ bool vis[MAXN];//访问标记 int ancestor[MAXN];//祖先 struct Edge { int to,next; }edge[MAXN*2]; int head[MAXN],tot; void addedge(int u,int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } struct Query { int q,next; int index;//查询编号 }query[MAXQ*2]; int answer[MAXQ];//存储最后的查询结果，下标0~Q-1 int h[MAXQ]; int tt; int Q; void add_query(int u,int v,int index) { query[tt].q = v; query[tt].next = h[u]; query[tt].index = index; h[u] = tt++; query[tt].q = u; query[tt].next = h[v]; query[tt].index = index; h[v] = tt++; } void init() { tot = 0; memset(head,-1,sizeof(head)); tt = 0; memset(h,-1,sizeof(h)); memset(vis,false,sizeof(vis)); memset(F,-1,sizeof(F)); memset(ancestor,0,sizeof(ancestor)); } void LCA(int u) { ancestor[u] = u; vis[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { int v = edge[i].to; if(vis[v])continue; LCA(v); bing(u,v); ancestor[find(u)] = u; } for(int i = h[u];i != -1;i = query[i].next) { int v = query[i].q; if(vis[v]) { answer[query[i].index] = ancestor[find(v)]; } } } bool flag[MAXN]; int Count_num[MAXN]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; int u,v,k; while(scanf("%d",&n) == 1) { init(); memset(flag,false,sizeof(flag)); for(int i = 1;i <= n;i++) { scanf("%d:(%d)",&u,&k); while(k--) { scanf("%d",&v); flag[v] = true; addedge(u,v); addedge(v,u); } } scanf("%d",&Q); for(int i = 0;i < Q;i++) { char ch; cin>>ch; scanf("%d %d)",&u,&v); add_query(u,v,i); } int root; for(int i = 1;i <= n;i++) if(!flag[i]) { root = i; break; } LCA(root); memset(Count_num,0,sizeof(Count_num)); for(int i = 0;i < Q;i++) Count_num[answer[i]]++; for(int i = 1;i <= n;i++) if(Count_num[i] > 0) printf("%d:%d\n",i,Count_num[i]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Curling 2.0 (poj 3009 dfs)	下一篇：阻塞IO的理解

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: