Submission #1108092

#TimeUsernameProblemLanguageResultExecution timeMemory
1108092overwatch9Cijanobakterije (COCI21_cijanobakterije)C++17
70 / 70
52 ms11852 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
vector <int> adj[maxn];
bool vis[maxn];
int node = 0, max_dis = -1;
void dfs(int s, int p, int d) {
    if (d > max_dis) {
        node = s;
        max_dis = d;
    }
    vis[s] = true;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs(i, s, d+1);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector <pair <int, int>> endpoints;
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            continue;
        max_dis = -1;
        endpoints.emplace_back();
        dfs(i, i, 0);
        endpoints.back().first = node;
        max_dis = -1;
        dfs(node, node, 0);
        endpoints.back().second = node;
    }

    for (int i = 0; i + 1 < (int)endpoints.size(); i++) {
        int a = endpoints[i].second, b = endpoints[i+1].first;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    max_dis = -1;
    dfs(endpoints.back().second, 0, 0);
    cout << max_dis+1 << '\n';

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...