Submission #1268731

#TimeUsernameProblemLanguageResultExecution timeMemory
1268731s1zzl3Cijanobakterije (COCI21_cijanobakterije)C++20
36 / 70
1093 ms9284 KiB
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
typedef long long ll;
const int MAXN = 1e5+5;

int n,m;
vector<int> graph[MAXN];
bool visited[MAXN];
int dist[MAXN];

void dfsMark(int u) {
    visited[u] = true;
    for (int v : graph[u]) {
        if(!visited[v]) dfsMark(v);
    }
}

void dfsDist(int u, int pre) {
    for (int v : graph[u]) {
        if(v != pre) {
            dist[v] = dist[u] + 1;
            dfsDist(v,u);
        }
    }
}

int calcDiameter(int start) {
    fill(dist, dist+n+1, -1);
    dist[start] = 0;
    dfsDist(start,-1);
    int far = start;
    for (int i=1; i<=n; i++) {
        if(dist[i] > dist[far]) far = i;
    }
    fill(dist, dist+n+1, -1);
    dist[far] = 0;
    dfsDist(far,-1);

    int diam = 0;
    for (int i=1; i<=n; i++) {
      diam = max(diam, dist[i]);
    }
    return diam+1; 
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int u,v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    ll res = 0;
    fill(visited, visited+n+1, false);
    for (int i=1; i<=n; i++) {
        if(!visited[i]) {
            dfsMark(i);
            res += calcDiameter(i);
        }
    }

    cout << res << nl;
}
#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...