dotcpp0692261

用户名：dotcpp0692261

访问量：77

签　名：

等　　级
排　　名	5294
经　　验	1519
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	辽宁大学
专　　业

　　自我简介：

TA的其他文章

tarjan的离线做法
浏览：21

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

tarjan的离线做法

　　作者: dotcpp0692261　　　　发表时间：2024-06-24 15:18:09 浏览：21　|　评论：0　

原题链接：信息学奥赛一本通T1552-点的距离

刚学习tarjan求最近公共祖先，以此题记录
要求的两点距离可用两点深度之和减去两点公共祖先节点的深度，即：
d[x,y]=d[0,x]+d[0,y]-2*d[0,p]

~~~
#include<bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int N=100010,M=2*N;
int h[N],e[M],ne[M],idx;
vector<pii>query[N];
int res[N];
int p[N];
int st[N];
int d[N];
int n,m;
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            d[j]=d[u]+1;
            dfs(j,u);
        }
    }
}
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
void tarjan(int u)
{
    st[u]=1;//开始进行中的标记为1
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j]){//如果为0就把它开始
        tarjan(j);
        p[j]=u;}
    }
    for(auto i:query[u])
    {
        int y=i.first,id=i.second;
        if(st[y]==2)
        {
            int ace=find(y);
            res[id]=d[u]+d[y]-2*d[ace];
        }
    }
    st[u]=2;//搜索完成就标记为2
}
int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    cin>>m;
    for(int i=1;i<=m;i++)//把所有询问保存
    {
        int a,b;
        cin>>a>>b;
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }
    for(int i=1;i<=n;i++)p[i]=i;//并查集初始化
    dfs(1,-1);//先求出每个点的深度
    tarjan(1);
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}
~~~

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

dotcpp0692261

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C二级辅导-求偶数和（C语言代码）

tarjan的离线做法

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-求函数值（C语言代码）

奖学金（C++代码）

C语言训练-大、小写问题（C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【数组的距离】（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

简单的a+b （C语言代码）

完数（C语言代码）

dotcpp0692261

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

tarjan的离线做法

评论区

精彩推荐

点我有惊喜！你懂得！

C语言训练-求函数值 （C语言代码）

奖学金 （C++代码）

C语言训练-大、小写问题 （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

【数组的距离】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.1 （C++代码）

简单的a+b （C语言代码）

完数 （C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

C语言训练-求函数值（C语言代码）

奖学金（C++代码）

C语言训练-大、小写问题（C语言代码）

【数组的距离】（C语言代码）

完数（C语言代码）