제출 #872492

#제출 시각아이디문제언어결과실행 시간메모리
872492HossamHero7Cijanobakterije (COCI21_cijanobakterije)C++14
70 / 70
32 ms8344 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e5+5;
vector<int> adj[N];
int dep[N];
int dep2[N];
int vis[N];
int bfs(int src){
    vis[src] = 1;
    queue<int> q;
    q.push(src);
    pair<int,int> mxDep {0,src};
    while(q.size()){
        int node = q.front();       q.pop();
        for(auto ch : adj[node]){
            if(vis[ch]) continue;
            q.push(ch);
            vis[ch] = 1;
            dep[ch] = dep[node] + 1;
            mxDep = max(mxDep,{dep[ch],ch});
        }
    }
    q.push(mxDep.second);
    vis[mxDep.second] = 2;
    int ret = 1;
    while(q.size()){
        int node = q.front();       q.pop();
        for(auto ch : adj[node]){
            if(vis[ch] == 2) continue;
            q.push(ch);
            vis[ch] = 2;
            dep2[ch] = dep2[node] + 1;
            ret = max(ret , dep2[ch] + 1);
        }
    }
    return ret;
}
void solve(){
    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);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        ans += bfs(i);
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
#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...