Cod sursa(job #1887306)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 21 februarie 2017 15:15:52
Problema Zvon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <vector>
#define N 100005
using namespace std;

vector<int> graf[N];
int teste,n,i,a,b,sol;
int t[N];               //t[i]=timpul necesar subarboreluj care incepe cu i pentru a trimite informatia
bool viz[N];

void dfs(int x,int tata)
{

    int i,tmax,nr_tmax;

    viz[x]=true;
    tmax=-1;nr_tmax=0;

    for(i=0;i<graf[x].size();i++)
    {
        if(!viz[graf[x][i]])
            dfs(graf[x][i],x);
        if(graf[x][i]!=tata)
        {
            if(t[graf[x][i]]==tmax)
                nr_tmax++;
            if(t[graf[x][i]]>tmax)
            {
                nr_tmax=1;
                tmax=t[graf[x][i]];
            }
        }
    }

    //printf("%d %d\n",tmax,nr_tmax);

    t[x]=tmax+nr_tmax;

    if(tmax==-1)
        t[x]=0;
}

void sterge()
{
    for(int i=1;i<=n;i++)
    {
        viz[i]=false;
        graf[i].clear();
        t[i]=0;
    }
}

int main()
{
    FILE *f1,*f2;
    f1=fopen("zvon.in","r");
    f2=fopen("zvon.out","w");

    fscanf(f1,"%d",&teste);

    while(teste--)
    {
        ///citire
        fscanf(f1,"%d",&n);
        for(i=1;i<n;i++)
        {
            fscanf(f1,"%d%d",&a,&b);
            graf[a].push_back(b);
            graf[b].push_back(a);
        }

        ///rezolvare

        sol=0;
        for(i=1;i<=n;i++)
        {
            if(!viz[i])
                dfs(i,0);
            if(t[i]>sol)
                sol=t[i];
        }
        fprintf(f2,"%d\n",sol);

        sterge();
    }

    return 0;
}