Cod sursa(job #2667724)

Utilizator zaBogdanZavadovschi Bogdan zaBogdan Data 3 noiembrie 2020 19:33:26
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int maxNr = 1e5+10;
int last=-1,diam=-1;
vector<int> v[maxNr];


void bfs(int nod){
	int counter[maxNr];
	bool viz[maxNr];
	memset(counter, 0, sizeof(counter));
	memset(viz, 0, sizeof(viz));
	queue<int> q;
	q.push(nod);
	viz[nod]=1;
	counter[nod]=0;
	while(!q.empty()){
		int aNod = q.front();
		q.pop();
		for(auto it: v[aNod])
			if(!viz[it]){
				viz[it]=1;
				counter[it] = counter[aNod]+1;
				q.push(it);
				last=it;
				diam = counter[it];
			}
	}
}


int main(){
	int n;
	ifstream f("darb.in");
	f >> n;
	for(int i=0;i<n;i++){
		int x,y;
		f >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	f.close();
	bfs(1);
	bfs(last);
	ofstream g("darb.out");
	g << diam+1;
	g.close();
    //linux output debug.
    cout << '\n';
    return 0;
}