Cod sursa(job #2721728)

Utilizator LaureniuNeghina Laurentiu Laureniu Data 12 martie 2021 10:22:06
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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();
        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]];
            }
        }
        q.pop();
    }
}
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();
}