Cod sursa(job #2800895)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 14 noiembrie 2021 12:55:27
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream f("darb.in");
ofstream g("darb.out");
 
const int NMAX=1e5+5;
int n, last, diametru, cnt[NMAX];
vector<int> G[NMAX], res;
 
void bfs(int nod){
    bool vis[NMAX]={0};
    vis[nod]=1;
    memset(cnt, 0, NMAX);
    cnt[nod]=0;
    queue<int> q;
    q.push(nod);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto i : G[x]){
            if(!vis[i]){
                q.push(i);
                vis[i]=1;
                last=i;
                cnt[i]=cnt[x]+1;
                diametru=cnt[i];
            }
        }
    }
}
 
void back(int nod){
    int vis[NMAX]={0};
    vis[nod]=1;
    queue<int> q;
    q.push(nod);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto i : G[x]){
            if(!vis[i] && cnt[x]-1==cnt[i]){
                res.push_back(i);
                q.push(i);
                vis[i]=1;
            }
        }
    }
}
 
int main(){
    f >> n;
    int k=n-1;
    while(k--){
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs(1);
    bfs(last);
    g << diametru + 1<< "\n";
    // res.push_back(last);
    // back(last);
    // for(auto i : res){
    //     g << i << " ";
    // }
    return 0;
}