Cod sursa(job #2812271)

Utilizator bogdan2405Strat Bogdan-Valentin bogdan2405 Data 4 decembrie 2021 11:55:45
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include<bits/stdc++.h>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

vector<int> adjList[100001];
vector<int> visited,dist;
queue<int> q;
int varfUltim,diametru=0;

	
int distanta=0;
 
void BFSLungime(int x){
    int i;
    q.push(x);
    varfUltim=x;
    if(visited[x]==0){
        dist[x-1]=distanta;
    visited[x]++;
     distanta++;
    }
   
 
    while(!q.empty()){
        int first=q.front();
        varfUltim=first;
        q.pop();
 
        for(i=0;i<adjList[first].size();++i){
            if(visited[adjList[first][i]]==0){
                visited[adjList[first][i]]++;
                dist[adjList[first][i]]=dist[first]+1;
                q.push(adjList[first][i]);
            }
        }
       
    }
 
}

void BFS(int x){
    int i;
    varfUltim=x;
    q.push(x);

     while(!q.empty()){
        int first=q.front();
        varfUltim=first;
        q.pop();
 
        for(i=0;i<adjList[first].size();++i){
            if(visited[adjList[first][i]]==0){
                visited[adjList[first][i]]++;
                
                q.push(adjList[first][i]);
               
            }
        }
        
       
    }
 
}
int main(){
    int n,a,b,i;
    f>>n;
    for(i=0;i<n-1;++i){
        visited.push_back(0);
        f>>a>>b;
        adjList[a-1].push_back(b-1);
        adjList[b-1].push_back(a-1);
    }

    visited.push_back(0);

    BFS(0);
    diametru=0;
    visited.clear();
    visited.assign(n,0);
    dist.assign(n,0);
    int varf1=varfUltim;
    BFSLungime(varf1);
    int varf2=varfUltim;
    diametru=dist[varf2]+1;
    g<<diametru;
    return 0;
}