北邮OJ-257- 最近公共祖先-14软院上机C

    xiaoxiao2021-03-25  18

      本题的思路是利用树的双亲表示法(并查集模板)进行寻根(findRoot方法)压栈,把每一级的父节点都压栈。然后从上往下逐一比对即可。

    Problem C. 最近公共祖先 题目描述 给出一棵有N个节点的有根树TREE(根的编号为1),对于每组查询,请输出树上节点u和v的最近公共祖先。 最近公共祖先:对于有向树TREE的两个结点u,v。最近公共祖先LCA(TREE u,v)表示一个节点x,满足x是u、v的祖先且x的深度尽可能大。 输入格式 输入数据第一行是一个整数T(1<=T<=100),表示测试数据的组数。 对于每组测试数据: 第一行是一个正整数N(1<=N<=100),表示树上有N个节点。 接下来N-1行,每行两个整数u,v(1<=u,v<=N),表示节点u是v的父节点。 接下来一行是一个整数M(1<=M<=1000),表示查询的数量。 接下来M行,每行两个整数u,v(11<=u,v<=N),表示查询节点u和节点v的最近公共祖先。 输出格式 对于每个查询,输出一个整数,表示最近公共祖先的编号, 输入样例 2 3 1 2 1 3 1 2 3 4 1 2 1 3 3 4 2 2 3 3 4 1 1 3

    #include <cstdio> #include <stack> #define MAXSIZE 500 using namespace std; struct Set{ //UnionFindSet 从0开始 int root[MAXSIZE]; int setSize; int initSet(int setSize){ this->setSize=setSize; for (int i=0;i<setSize;i++){ root[i]=-1; } } int findRoot(int x,stack<int> &s){ while (root[x]!=-1){ s.push(x); x=root[x]; } s.push(x); return x; } }; int main(){ int t,n,m; int u,v; Set set; scanf("%d",&t); stack<int> fa1,fa2; for (int time=0;time<t;time++){ //initiate scanf("%d",&n); set.initSet(n); //input for (int i=0;i<n-1;i++){ scanf("%d%d",&u,&v); u--;v--;//adjust set.root[v]=u; } //query scanf("%d",&m); for (int i=0;i<m;i++){ //initiate while (!fa1.empty()) fa1.pop(); while (!fa2.empty()) fa2.pop(); scanf("%d%d",&u,&v); u--;v--;//adjust //search set.findRoot(u,fa1); set.findRoot(v,fa2); //match //preprocess int root1,root2,LCA; LCA=fa1.top(); fa1.pop(); fa2.pop(); while (!fa1.empty()&&!fa2.empty()){ root1=fa1.top(); root2=fa2.top(); fa1.pop(); fa2.pop(); if (root1==root2) LCA=root1; else break; } //output printf("%d\n",LCA+1); } } return true; }
    转载请注明原文地址: https://ju.6miu.com/read-50271.html

    最新回复(0)