Cod sursa(job #2666730)

Utilizator GeoDinBacauTofan George GeoDinBacau Data 2 noiembrie 2020 14:29:23
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("darb.in");
ofstream fcout("darb.out");

vector<int>nod[100003];
int n,maxl=-1,maxnod;
bool ap[100003];

void dfs(int k, int l)
{
    if (ap[k])
        return;
    ap[k]=1;
    l++;
    //cout<<k<<", ";
    if(l>maxl)
        maxl=l,maxnod=k;
    for(int i=0;i<nod[k].size();i++)
        dfs(nod[k][i],l);
}

void clear_ap()
{
    for(int i=1;i<=n;i++)
        ap[i]=0;
}

void show_ap()
{
    for(int i=1;i<=n;i++)
        cout<<ap[i]<<' ';
    cout<<endl;
}

int main()
{
    int a,b;
    fcin>>n;
    for(int i=1;i<n;i++){
        fcin>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
//sort
    for(int i=1;i<=n;i++)
        sort(nod[i].begin(),nod[i].end());
//first search
    dfs(nod[a][0],0);
    //cout<<maxnod<<':'<<' '<<maxl<<endl<<endl;
    //show_ap();
    clear_ap();
    maxl=-1;
    dfs(maxnod,0);
    //cout<<maxnod<<':'<<' '<<maxl<<endl;
    fcout<<maxl;
}

/**
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("date.txt");
ofstream fcout("dfs.out");

vector<int>nod[110];
int n,m,x;
bool ap[110];

void DFS(int k)
{
    if(ap[k])
        return;
    cout<<k<<' ';
    ap[k]=1;
    for(int i=0;i<nod[k].size();i++)
        DFS(nod[k][i]);
}

int main()
{
    cin>>n>>m>>x;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a); //graf neorientat
    }

//    for(int i=1;i<=n;i++)
//        cout<<i<<": "<<nod[i].size()<<endl;

//    for(int i=1;i<=n;i++){
//        cout<<i<<": ";
//        for(int j=0;j<nod[i].size();j++)
//            cout<<nod[i][j]<<' ';
//        cout<<endl;
//    }

    for(int i=1;i<=n;i++)
        sort(nod[i].begin(),nod[i].end());

    DFS(x);

    return 0;
}
*/