Cod sursa(job #2721731)

Utilizator LaureniuNeghina Laurentiu Laureniu Data 12 martie 2021 10:24:51
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
vector<vector<int> > v;
int c[1000001]={0},last=1,viz[1000001]={0},diametru=0;
queue<int> q;
void bfs(int nod){q.push(nod);c[nod]=0;viz[nod]=1;while(!q.empty()){int nodcurent=q.front();q.pop();for(int i=0;i<v[nodcurent].size();i++){if(viz[v[nodcurent][i]]==0){viz[v[nodcurent][i]]=1;c[v[nodcurent][i]]=c[nodcurent]+1;q.push(v[nodcurent][i]);last=v[nodcurent][i];diametru=c[v[nodcurent][i]];}
}}
}
int main(){
    int n,m;
    ifstream f("darb.in");
    ofstream g("darb.out");
    f>>m;
    v = vector<vector<int> >(m+1);
    for(int x,y,i=0;i<m;i++){
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs(1);
    memset(viz,0,sizeof viz);
    bfs(last);
    g<<diametru+1;
    f.close();
    g.close();
}