Description

【题目描述】
给出一个有 $n$ 个点 $m$ 条路径的无向连通图，求无向连通图的直径。

【输入格式】
第一行两个整数 $n \ m$（$1≤n≤5×10^4$，$0≤m≤10^4$），$2≤k≤10^3$。
下来 $m$ 行，每行表示一条路径。
每行：开始有一个整数 $k$，代表在这条路径上的顶点个数。下来是 $k$ 个 $1$ 到 $n$ 之间的整数，分别对应了一个顶点，相邻的顶点表示存在一条无向边（每条边长度为1）。

【输出格式】
输出一个数，表示无向连通图的直径长度。

【输入样例1】
15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10

【输出样例1】
8

【样例1提示】
对第一个样例的说明：如图，$6$ 号点和 $12$ 号点的最短路径长度为 $8$，所以这张图的直径为 $8$。


【输入样例2】
10 1
10 1 2 3 4 5 6 7 8 9 10

【输出样例2】
9

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
vector<int>G[N];
int tsp,dfn[N],low[N],fa[N];
int ans,d[N],td[N*2],q[N];
void solve(int x,int y)
{
    int cnt=0;for(int z=y;z!=fa[x];z=fa[z]) td[++cnt]=d[z];
    for(int i=1;i<=cnt;i++) td[i+cnt]=td[i];
    int l=1,r=1;q[1]=1;
    for(int i=2;i<=cnt*2;i++)
    {
        while(l<=r&&i-q[l]>cnt/2) l++;
        ans=max(ans,td[i]+td[q[l]]+i-q[l]);
        while(l<=r&&td[i]-i>=td[q[r]]-q[r]) r--;
        q[++r]=i;
    }
    for(int i=1;i<=cnt;i++) d[x]=max(d[x],td[i]+min(i,cnt-i));
}
void tarjan(int x,int xfa)
{
    dfn[x]=low[x]=++tsp;
    for(int y:G[x])if(y!=xfa)
    {
        if(!dfn[y])
        {
            fa[y]=x;
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        else low[x]=min(low[x],dfn[y]);
        if(dfn[x]<low[y])
        {
            ans=max(ans,d[x]+d[y]+1);
            d[x]=max(d[x],d[y]+1);
        }
    }
    for(int y:G[x])if(fa[y]!=x)
    {
        if(dfn[x]<dfn[y]) solve(x,y);
    }
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    while(m--)
    {
        int k,x,y;scanf("%d%d",&k,&x);k--;
        while(k--)
        {
            scanf("%d",&y);
            G[x].push_back(y);G[y].push_back(x);
            x=y;
        }
    }
    tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	ans=0;tarjan(1,0);
    printf("%d\n",ans);
    return 0;
}

Source

省选/NOI−