牛客小白月赛6C-桃花（DFS/BFS求树的直径）

时间：2022-08-29 02:27:48

链接：https://www.nowcoder.com/acm/contest/136/C

来源：牛客网

桃花
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

桃花一簇开无主，可爱深红映浅红。

                                        ——《题百叶桃花》

桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。

输入描述:

第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数a

i

,b

i

 ，表示桃树上的节点a

i

,b

i

之间有一条边。

输出描述:

第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。

输入例子:
3

1 2

2 3
输出例子:
3

-->

示例1

输入

复制

3

1 2

2 3

输出

复制

3
示例2

输入

复制

3

1 2

1 3

输出

复制

3
示例3

输入

复制

4

1 2

2 3

3 4

输出

复制

4

备注:

对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。

解题思路：求树直径的裸题，两遍dfs，第⼀遍从任⼀点开始，找到距这个点最远的点，他⼀定是直径的⼀端，然 后从这个点开始再dfs，找到最远的距离，输出即可。可以用DFS，也可以用BFS，节点数比较多，需要用链式前向星的方法存储边。
DFS代码：
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

struct node{

    int to,next;

}edge[*maxn];

int cnt=;

int vis[maxn],head[maxn],dis[maxn];

void add(int u,int v)

{

    edge[++cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

void dfs(int x)

{

    vis[x]=;

    for(int i=head[x];i;i=edge[i].next)

    {

        if(!vis[edge[i].to])

        {

            dis[edge[i].to]=dis[x]+;

            dfs(edge[i].to);

        }

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        memset(head,-,sizeof(head));

        memset(vis,,sizeof(vis));

        memset(dis,,sizeof(dis));

        for(int i=;i<n;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

        }

        dis[]=;

        dfs();

        int pos=;

        for(int i=;i<=n;i++)

        {

            if(dis[i]>dis[pos])

                pos=i;

        }

        memset(vis,,sizeof(vis));

        dis[pos]=;

        dfs(pos);

        int ans=;

        for(int i=;i<=n;i++)

        {

            if(dis[i]>ans)

            ans=dis[i];

        }

        printf("%d\n",ans);

    }

}

BFS代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

struct node{

    int to,next;

}edge[*maxn];

int cnt=,ans;

int vis[maxn],head[maxn],dis[maxn];

queue<int> que;

void add(int u,int v)

{

    edge[++cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

int bfs(int x)

{

    memset(vis,,sizeof(vis));

    dis[x]=;

    que.push(x);

    while(!que.empty())

    {

        int p=que.front();

        que.pop();

        for(int i=head[p];i!=-;i=edge[i].next)

        {

            if(!vis[edge[i].to])

            {

                dis[edge[i].to]=dis[p]+;

                que.push(edge[i].to);

                vis[edge[i].to]=;

                ans=max(ans,dis[edge[i].to]);

            }

        }

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        memset(head,-,sizeof(head));

        memset(dis,,sizeof(dis));

        for(int i=;i<n;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            add(u,v);

            add(v,u);

        }

        ans=;

        bfs();

        int pos=;

        for(int i=;i<=n;i++)

        {

            if(dis[i]>dis[pos])

            pos=i;

        }

        ans=;

        bfs(pos);

        printf("%d\n",ans);

    }

    return ;

}

相关文章