用的离线算法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);
    }
    ;
}

最新文章

  1. Nginx配置性能优化
  2. 20145205《Java程序设计》第四次实验:Android环境搭建
  3. VA01复制单据,更新定价日期和价格
  4. Emmet 使用说明。
  5. 字符串s中从第i个位置起取长度为len的子串,函数返回子串链表
  6. C++模板【转】
  7. XML 命名空间
  8. 【转】Android版本和API Level对应关系
  9. http发送post请求
  10. ASP.NET MVC 使用MSBuild生成的几个注意事项
  11. poj1837挂砝码
  12. Cordova的搭建
  13. ArcCore重构-目标文件结构化
  14. 蓝桥杯_算法训练_ALGO10_集合运算
  15. Egret 4.x 和 5.x 项目共存的方法
  16. Vue常见指令
  17. 电商中的库存管理实现-mysql与redis
  18. 通达OA2008优化前端web为lnmp环境及后续优化
  19. oracle 建用户
  20. IT农民的开发人员工具清单(2013年)

热门文章

  1. GPIO—位带操作
  2. oracle中空值null的判断和转换:NVL的用法
  3. CSS学习笔记(7)--html页面的CSS、DIV命名规则
  4. java web 自定义filter
  5. Spring Cloud都做了哪些事
  6. UP与瀑布模型
  7. linux -- Ubuntu network-manager
  8. LR的响应时间与使用IE所感受时间不一致的讨论(摘抄补充)
  9. Python使用pycurl获取http的响应时间
  10. springmvc传递有特殊字符的路径参数