Cod sursa(job #2800892)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 14 noiembrie 2021 12:52:59
Problema Diametrul unui arbore Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 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], dad[NMAX], finish;
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;
                cnt[i]=cnt[x]+1;
                if(cnt[i] > diametru) {
					diametru = cnt[i];
					last = i;
				}
            }
        }
    }
}
 
void back(int nod){
    bool vis[NMAX]={0};
	memset(cnt, 0, NMAX);
    vis[nod]=1;
    queue<int> q;
    q.push(nod);
	diametru = 0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto i : G[x]){
            if(!vis[i]){
                vis[i] = 1;
				cnt[i] = cnt[x] + 1;
				dad[i] = x;
				if(cnt[i] > diametru) {
					diametru = cnt[i];
					finish = i;
				}
				q.push(i);
            }
        }
    }
}
 
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);
	//cout << last << '\n';
    back(last);
    g << diametru + 1 << '\n';
	//cout << finish << ' ';
    // while(finish != 0) {
	// 	res.push_back(finish);
	// 	finish = dad[finish];
	// }
	// reverse(res.begin(), res.end());
	// for(int i = 0; i < (int)res.size(); i++) {
	// 	g << res[i] << ' ';
	// }

    return 0;
}