POJ1330Nearest Common Ancestors最近公共祖先LCA问题
2024-10-20 04:03:29
用的离线算法Tarjan
该算法的详细解释请戳
http://www.cnblogs.com/Findxiaoxun/p/3428516.html
做这个题的时候,直接把1470的代码copy过来,改了改输入输出。这个的难度比那个低。
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; ; int father[MAXN],ancestor[MAXN]; bool visit[MAXN]; int ans[MAXN]; vector<int> map[MAXN];//save the tree int n,t,root,sx,sy; bool indegree[MAXN];//the indegree to find the root int getfather(int v){//path compression if(father[v]==v)return v; return father[v]=getfather(father[v]); } void aunion(int u,int v){ int fv=getfather(v),fu=getfather(u); father[fv]=fu; } bool isit(int a,int b){ if(a==sx&&b==sy)return true; return false; } void LCA(int id){ int len=map[id].size(); int son; ;i<len;i++){ son=map[id][i]; LCA(son); aunion(id,son); } visit[id]=; if(visit[sy]&&id==sx){ printf("%d\n",father[getfather(sy)]); return; }else{//attention:this way if(visit[sx]&&id==sy){ printf("%d\n",father[getfather(sx)]); return; } } } void init(){ int x,y,z; scanf("%d",&n); //initialize all the vars ;i<=n;i++){ map[i].clear(); } memset(visit,,sizeof(visit)); memset(ans,,sizeof(ans)); memset(indegree,,sizeof(indegree)); ;i<=n;i++)father[i]=i; ;i<n-;i++){ scanf("%d%d",&x,&y); indegree[y]=; map[x].push_back(y); } scanf("%d%d",&sx,&sy); ;i<=n;i++)if(!indegree[i])root=i;//find the root;warning:the 0 } int main(){ int t; scanf("%d",&t); while(t--){ init(); LCA(root); } ; }
最新文章
- Nginx配置性能优化
- 20145205《Java程序设计》第四次实验:Android环境搭建
- VA01复制单据,更新定价日期和价格
- Emmet 使用说明。
- 字符串s中从第i个位置起取长度为len的子串,函数返回子串链表
- C++模板【转】
- XML 命名空间
- 【转】Android版本和API Level对应关系
- http发送post请求
- ASP.NET MVC 使用MSBuild生成的几个注意事项
- poj1837挂砝码
- Cordova的搭建
- ArcCore重构-目标文件结构化
- 蓝桥杯_算法训练_ALGO10_集合运算
- Egret 4.x 和 5.x 项目共存的方法
- Vue常见指令
- 电商中的库存管理实现-mysql与redis
- 通达OA2008优化前端web为lnmp环境及后续优化
- oracle 建用户
- IT农民的开发人员工具清单(2013年)