技术教程 编程代码 AcWing 4799. 最远距离题解 正文

AcWing 4799. 最远距离题解

2023-08-05,,

请看：

我们规定，如果一个无向连通图满足去掉其中的任意一条边都会使得该图变得不连通，则称该图为有效无向连通图。

去掉一条边就不连通了，这不就是树吗？

（否则如果是图（就是不是树的图）的话，一定有环，拆了一条边从另一端还可以去，就不会不连通了）。

那么最长距离就变为：树的直径了。

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

struct Edge {

    int to, next;

}e[M];

int head[N], idx;

void add(int a, int b) {

    idx++, e[idx].to = b, e[idx].next = head[a], head[a] = idx;

}

void dfs(int u, int fa, int& maxver, int& maxstep, int step) {

    if (maxstep < step) {

        maxstep = step;

        maxver = u;

    }

    for (int i = head[u]; i; i = e[i].next) {

        int to = e[i].to;

        if (to == fa) continue;

        dfs(to, u, maxver, maxstep, step + 1);

    }

}

int n, m;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {

        int a, b;

        cin >> a >> b;

        add(a, b), add(b, a);

    }

    // dfs(1, 0);

    int mv = 0, ms = 0, mv1 = 0, ms1 = 0;

    dfs(1, 0, mv, ms, 1);

    dfs(mv, 0, mv1, ms1, 1);

    cout << ms1 - 1 << '\n';

    return 0;

}

AcWing 4799. 最远距离题解的相关教程结束。

《AcWing 4799. 最远距离题解.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!