#3wa了,求调,谢谢
查看原帖
#3wa了,求调,谢谢
1112952
Au_Gold楼主2024/8/24 12:50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 3e5 + 5, M = 3e5 + 5, mod = 7;
ll n, m, fr, to, h[N], ind;
struct Edge
{
    ll to, nx;
} e[M * 2];//图
void add(ll fr, ll to)
{
    e[ind] = {to, h[fr]};
    h[fr] = ind++;
}
vector<ll> tr[N];//树
ll dfn[N], low[N], tot, sta[N], insta[N], top, scc[N], siz[N], cnt;
void tarjan(ll fr, ll in)
{
    dfn[fr] = low[fr] = ++tot;
    sta[++top] = fr, insta[fr] = 1;
    for (ll i = h[fr]; ~i; i = e[i].nx)
    {
        to = e[i].to;
        if (!dfn[to])
        {
            tarjan(to, i);
            low[fr] = min(low[fr], low[to]);
            // if(dfn[fr]<low[to])
        }
        else if (i != (in ^ 1))
            low[fr] = min(low[fr], dfn[to]);
    }
    if (dfn[fr] == low[fr])
    {
        cnt++;
        do
        {
            to = sta[top--], insta[to] = 0;
            scc[to] = cnt, siz[cnt]++;
        } while (fr != to);
    }
}

ll dep[N],x, y, duan,vis[N];
void dfs(ll self, ll fath)//求直径的
{
    for (ll to : tr[self])
    {
        if (to == fath||vis[to])
            continue;
        vis[to] = 1;
        dep[to] = dep[self] + 1;
        if (dep[to] > dep[duan])
            duan = to;
        dfs(to, self);
    }
}
void getDiameter()
{
    dfs(1, 0); // duan为直径端点
    x = duan, duan = 0, dep[x] = 0;//先找到一个端点x
    memset(vis, 0, sizeof(vis));
    dfs(x, 0);
    y = duan;//再找另一个端点y
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        cin >> fr >> to;
        add(fr, to);
        add(to, fr);
    }
    for (ll i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, -1);
    //建树
    for (ll fr = 1; fr <= n; fr++)
        for (ll i = h[fr]; ~i; i = e[i].nx)
        {
            to = e[i].to;
            if (scc[fr] != scc[to])
                    tr[scc[fr]].push_back(scc[to]);
        }
    //求直径
    getDiameter();
    cout << dep[y] << endl;

    return 0;
}
2024/8/24 12:50
加载中...