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; } }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1226http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1637http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1703http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1312Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 856首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1269朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1659题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2465AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1180二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2122网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 863trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 908bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1068我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2829zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1358染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 739线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 774快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3066斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1277本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 935针对Bellman-Ford算法效率比较低 ...
相关推荐
用C#实现的取得CellID和LAC的程序源代码!
SMAC LAC-1控制器参数
01 MSR810_MSR93X系列路由器L2TP (LAC---LNS模式)配置方法 02 ICG5000G_T_ICG6000系列路由器L2TP (LAC---LNS模式)配置方法 03 ICG2000D_ICG3000F系列路由器L2TP (LAC---LNS模式)配置方法 04 MSR2600-XX-X1_...
本文实现了对自适应队列编码的实现,自适应队列是一种高效的编码
基于java平台的运算,fiji插件,快速方便,苹果电脑mac最新版本。
4_散列算法_数字签名_数字证书 5_PKI架构_证书管理 6_ipsec协议介绍 7_ikev1协议精讲 8_ikev2协议讲解 9_site-to-site_vpn实验讲解 10_hub_spoke_策略模板 11_site-2-site_数字证书_数字信封认证 12_gre ...
资源来自pypi官网。 资源全名:LAC-2.0.5.tar.gz
SMAC LAC-1 DATASHEET SMAC LAC-1 数据手册pdf文档 LAC-1电缸驱动器手册
B-Lac_FighterBot
史脉可(SMAC) 双轴控制器LAC-25指令介绍pdf,史脉可(SMAC) 双轴控制器LAC-25指令介绍
URA_PCH与LAC的区别
SMAC LAC-1单轴控制器端口定义 音圈电机驱动器针脚定义
以LAC候选算法为例,通过伪造攻击的方法对其内部结构、认证机制和攻击原理进行了分析和描述,并对其原有结构进行了改进,使其能够有效地抵抗现有的伪造攻击。通过对其安全性进行分析,表明LAC算法改进方案能够有效...
需要提供给脚本MCC、MNC、LAC、CELLID信息,也可提供LAC或CELL的区间 信息,进行扫描。 使用说明: Usage: ./getlocal.sh --mcc={MCC} --mnc={MNC} --lac={LAC} --cid={CELLID} --radio=|wcdma> --flac={FROM} -...
使用Mapinfo中Voronoi算法自动生成LAC或BSC等边界图
LAC全称Lexical Analysis of Chinese,是百度自然语言处理部研发的一款联合的词法分析工具,实现中文分词、词性标注、专名识别等功能
这个项目的重点是为Linux和其他Unix提供商业质量的L2TP支持。 L2TP代表第2层隧道协议。 这是一个类似于PPTP的VPN。 L2TP经常与PPPoE竞争。
中国电信CDMA-全国SID_NID分配对应参照表
cell lac 基站数据
bi-lac-ssv