P8028 [COCI2021-2022#3] Cijanobakterije 题解

· · 题解

题目大意

现有一个森林图，随意添加边使它成为一棵树。求这棵树的直径。

思路

树的直径：树上最远两点间的距离。

我们可以把森林中每一棵树的直径两端连接起来。因为一棵树的直径原本就是这棵树中最长的链，所以在新树中也不可能存在比这条新的、用原来的树的直径组成的链更长的新链。那么很明显，答案就是该森林中所有树的直径的和。

那么怎么求出这个距离呢？求树的直径有很多方法，可以使用两遍 dfs 求直径的方法。

step 1

在树上随便选一个点作为起点，然后向它能到达的走去。记录下走过的点数。

step 2

找出从起点开始，步数最多的点，记录下来，作为下一次 dfs 的起点。

step 3

从刚才新的起点开始，继续搜索它能到达的点。最后距离新起点最远的点和新起点的距离就是这棵树的直径。

求出每棵树的直径，然后加起来就成了最终的答案。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,ans,res,id;
int in[100001];
bool vis[100001];
vector<int> g[100001];
void dfs(int x,int z)
{
    vis[x]=1;
    if(res<z) res=z,id=x;
    int si=g[x].size();
    for(int i=0;i<si;i++)
        if(!vis[g[x][i]]) dfs(g[x][i],z+1);
    return;
}
void sfd(int x,int f,int z)
{
    res=max(res,z);
    int si=g[x].size();
    for(int i=0;i<si;i++)
        if(g[x][i]!=f) sfd(g[x][i],x,z+1);
    return;
}
void wok(int x)
{
    res=0;dfs(x,1);
    res=0;sfd(id,id,1);
    ans+=res;
}
int main()
{
//  freopen("P8028.in","r",stdin);
//  freopen("P8028.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
        in[u]++,in[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]==1&&!vis[i]) wok(i);
        if(!in[i]) ans++;
    }
    printf("%d",ans);
    return 0;
}