Cod sursa(job #2444965)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 1 august 2019 23:07:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.4 kb
#include <bits/stdc++.h>
using namespace std;

class treeDiameter
{
private:
#define TREE_CHECK_CREATED(ret) if (!created) return ret
#define TREE_ERROR 4294967295
#define uint unsigned int
#define pb push_back
    std::vector<uint>*edges;
    bool created, *visited;
    uint n, edgeCount;
    bool df(uint k, uint lst)
    {
        visited[k] = true;
        for (uint i=0;i<edges[k].size();++i)
        {
            if (visited[edges[k][i]] && lst != edges[k][i]) return false;
            if (visited[edges[k][i]]) continue;
            return df(edges[k][i], k);
        }
        return true;
    }
    bool isTree()
    {
        if (edgeCount + 2 != n) return false;
        for (uint i=0;i<n;++i)
            visited[i] = false;
        return df(1, TREE_ERROR);
    }
    void dfs(uint k, uint lst, uint &maxx, uint &maxxN, uint act)
    {
        if (act > maxx)
            maxx = act, maxxN = k;
        for (uint i=0;i<edges[k].size();++i)
        {
            if (edges[k][i] == lst) continue;
            dfs(edges[k][i], k, maxx, maxxN, act + 1);
        }
    }
public:
    treeDiameter(): edges(nullptr), created(false), edgeCount(0) {}
    bool create(uint sz)
    {
        if (created) return false;
        edges = new std::vector<uint>[sz+2];
        if (edges == nullptr) return false;
        visited = new bool[sz + 2];
        if (visited == nullptr)
        {
            delete[] edges;
            return false;
        }
        n = sz + 1;
        created = true;
        return true;
    }
    bool addEdge(uint x, uint y)
    {
        TREE_CHECK_CREATED(false);
        if (x >= n || y >= n || !x || !y) return false;
        edges[x].pb(y);
        edges[y].pb(x);
        ++edgeCount;
        return true;
    }
    uint calcDiameter()
    {
        TREE_CHECK_CREATED(TREE_ERROR);
        if (!isTree()) return TREE_ERROR;
        uint ans = 0, node, altNode;
        dfs(1, TREE_ERROR, ans, node, 0);
        ans = 0;
        dfs(node, TREE_ERROR, ans, altNode, 0);
        return ans + 1;
    }
};

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    int n, x, y;
    scanf("%d",&n);
    treeDiameter tree;
    tree.create(n);
    for (int i=1;i<n;++i)
    {
        scanf("%d %d",&x,&y);
        tree.addEdge(x, y);
    }
    printf("%u\n", tree.calcDiameter());
    return 0;
}