Cod sursa(job #2813566)

Utilizator MihaiBirsanMihai Birsan MihaiBirsan Data 6 decembrie 2021 22:35:07
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.48 kb
#include <bits/stdc++.h>

#define Nmax 100010

using namespace std;
/*
ifstream fin("apm.in");
ofstream fout("apm.out");
*/
ifstream fin("darb.in");
ofstream fout("darb.out");

class Graf
{
private:
    vector<vector<int>> gr;   //graf -> lista de adiacenta
    vector<vector<int>> gr_t; //graf transpus
    int par[Nmax];
    int dim[Nmax];
    vector<int> topo;
    int dist[Nmax] = {-1};
    int viz[Nmax] ;
    int n;
    int m;
    int nr_componente_conexe = 0;

public:
    Graf(): n(0), m(0)
    {

    }

    Graf(int x, int y = 0): n(x), m(y)
    {

    }

    Graf(int x, int y, const vector<vector<int>>& v): n(x), m(y), gr(v)
    {

    }
    //dezvizitatam toate nodurile
    void nevizitate()
    {
        for(int i = 1; i <= n; i++)
            viz[i] = 0;
    }
    //bfs
    void BFS(int start)
    {
        int c[Nmax];
        int pr, ul;
        pr = 0;
        ul = -1;
        int n_curent;
        dist[start] = 0;
        c[++ul] = start;
        while(pr <= ul)
        {
            n_curent = c[pr++];
            for(auto i:gr[n_curent]) //verificam toti vecinii nodului curent
                if(dist[i] == -1)
                {
                    dist[i] = dist[n_curent] + 1;
                    c[++ul] = i;
                }
        }
    }
    //dfs
    void DFS(int x)
    {
        viz[x] = nr_componente_conexe;
        for(int i = 0; i < gr[x].size(); ++i)
        {
            if(viz[gr[x][i]] == 0)
            {
                viz[gr[x][i]] = 1;
                DFS(gr[x][i]);
            }
        }
    }
    //sortare topologica
    void sortare_topologica(int x)
    {
        viz[x] = 1;
        for(int i = 0; i < gr[x].size(); ++i)
        {
            if(viz[gr[x][i]] == 0)
                sortare_topologica(gr[x][i]);
        }
        topo.push_back(x);
    }

    void DFS2(int x,int ct,vector<vector<int>> ctc,  int comp[])
    {
        viz[x] = 1;
        comp[x] = ct;
        ctc[ct].push_back(x);
        for(int i = 0; i< gr_t[x].size(); i++)
        {
            if(viz[gr_t[x][i]] == 0)
            {
                DFS2(gr_t[x][i],ct,ctc,comp);
            }
        }
    }

    void componenteTareConexe(int ct, int comp[], const vector<vector<int>>& ctc)
    {
        nevizitate();
        for(int i=1;i<=n;++i)
        {
            if(viz[i] == 0)
            {
                sortare_topologica(i);
            }
        }
        reverse(topo.begin(), topo.end());
        for(auto i:topo)
        {
            if(comp[i] == 0)
            {
                ct += 1;
                DFS2(i, ct, ctc, comp);
            }
        }
    }
    //Havel Hakimi
    bool HavelHakimi(vector<int> &grade)
    {
        sort(grade.begin(), grade.end(), greater<>());
        while(grade.size() > 0)
        {
            if(grade[0] + 1 > grade.size())
                return false;

            for(int i = 1; i <= grade[0]; i++)
            {
                grade[i] -= 1;
                if(grade[i] < 0)
                {
                    return false;
                }
            }
            grade.erase(grade.begin());
            sort(grade.begin(), grade.end(), greater<>());
        }
        return true;
    }
    //Paduri de multimi disjuncte
    int findd(int x)
    {
        while(x != par[x])
        {
            x = par[x];
        }
        return x;
    }

    void unite(int x, int y)
    {
        x = findd(x);
        y = findd(y);
        if(dim[x] >= dim[y])
        {
            par[y] = x;
            dim[x] += dim[y];
        }
        else
        {
            par[x] = y;
            dim[y] += dim[x];
        }
    }

    void init()
    {
        for(int i=1; i<=n; i++)
        {
            par[i] = i;
            dim[i] = 1;
        }
    }

    //Arbore partial de cost minim -> folosim algoritmul kruskal
    vector<pair<int, pair<int, int>>> kruskal(vector<pair<int, pair<int, int>>>& muchii)
    {
        vector<pair<int, pair<int, int>>> subgr;
        sort(muchii.begin(), muchii.end());
        init();
        for(auto &muchie : muchii)
        {
            if(findd(muchie.second.first) != findd(muchie.second.second))
            {
                unite(muchie.second.first, muchie.second.second);
                subgr.push_back({muchie.first, {muchie.second.first, muchie.second.second}});
            }
        }
        return subgr;
    }

    //Diametrul unui arbore
    void dfsParcurgere(int x, int d, int &dmax, int &nmax)
    {
        if(d > dmax)
        {
            dmax = d;
            nmax = x;
        }
        viz[x] = 1;
        for(auto k:gr[x])
        {
            if(viz[k] == 0)
            {
                dfsParcurgere(k, d+1, dmax, nmax);
            }
        }
    }

    int diamentru()
    {
        int nmax = 0, dmax = 0;
        dfsParcurgere(1, 0, dmax, nmax);
        int n1 = nmax;
        nevizitate();
        dmax = 0;
        nmax = 0;
        dfsParcurgere(n1, 0, dmax, nmax);
        return dmax + 1;
    }
};

int main()
{
    //Diametrul unui arbore /////////////////////////////////////////////////////////////////
    int n, x ,y;
    fin >> n;
    vector<vector<int>> v(n + 1);
    for(int i = 1; i < n; i++)
    {
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    Graf graf(n, n-1, v);
    int sol = graf.diamentru();
    fout << sol;


}