Cod sursa(job #2821006)

Utilizator oporanu.alexAlex Oporanu oporanu.alex Data 21 decembrie 2021 22:59:10
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 13.64 kb
#include <bits/stdc++.h>
using namespace std;

/*class Edge{
    int i, j, cost;
    Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}

    friend bool operator<(const Edge& e1, const Edge& e2) {
          return e1.cost < e2.cost;
    }
    // util in ordonarea dupa cost
};
// o structura de tip muchie, utila in problema APM cand, aplicand algoritmul lui Kruskall
// avem nevoie sa sortam muchiile crescator dupa cost
*/

// in principiu util doar pt HavelHakimi
void countSort(vector<int>& input)
{
    map<int, int> freq;
    for (int x: input) {
        freq[x]++;
    }
    int i = 0;
    for (auto p: freq)
    {
        while (p.second--) {
            input[i++] = p.first;
        }
    }
}

bool HavelHakimi(vector<int> d){
        int n = d.size();
        int sum = 0;
        for(auto degree: d) {
            if(degree > n - 1)
                return false;
            sum += degree;
        }

        while(d.size()){
            countSort(d);
            int biggest = d[0];
            d.erase(d.begin());
            for(int i = 0; i < biggest; ++i)
                {
                    --d[i];
                    if(d[i] < 0){
                        return false;
                    }
                }
            }
        return true;
    }

class Graph {
public:
    int V;
    int E;
    vector<vector<pair<int, int>>> adj;
    // lista de adiacenta a nodului 'n' e formata din perechi de tipul
    // {vecin, cost}, unde cost = costul muchiei {n, vecin}.
    // daca graful n-are costuri pe muchii cost = 0, deoarece un graf
    // fara costuri pe muchii este un caz particular de graf cu costuri pe muhcii, unde toate costurile sunt = 0
    Graph(int, int, vector<vector<pair<int, int>>>);
    // constructorul care contine doar informatii de tipul
    // 'graful este orientat/neorientat si are/n-are costuri pe muchii'
    void build(int, int, vector<vector<pair<int, int>>>);
    // metoda care - mi construieste graful, initializandu - i numarul de noduri si muchii
    // dar si lista de adiacenta
    void DFSUtil(int, vector<bool>&, vector<int>&);
    // metoda ajutatoare pentru DFS, primeste ca parametrii nodul de unde incepe parcurgerea, vectorul care tine
    // minte nodurile vizitate / nevizitate (pe care il modifica) si insula curenta (pe care o formeaza, fiind de asemenea
    // transmisa prin referinta
    vector<int> DFS(int, vector<bool>&);
    // metoda care returneaza (intr-un vector) ordinea parcurgerii dfs incepand din nodul primit ca prim parametru.
    // de asemenea primeste si un parametru de tip vector de bool (true / false) care modifica nodurile vizitate
    // la parcurgerea curenta
    int connectedComponents();
    // metoda care - mi returneaza numarul de componente conexe dintr - un graf neorientat
    pair<vector<int>, vector<int>> bfs(int src);
    // returnez ordinea parcurgerii bfs, dar si
    // un vector de distante minime. Amandoua sunt relevante
    // si specifice parcurgerii in latime
    void dfForTopoSort(int, vector<bool>&, stack<int>&);
    // metoda df pentru sortare topologica, primeste ca argumente nodul de unde incepe aceasta parcurgere,
    // vectorul de care tine minte pentru noduri daca sunt vizitate / nevizitate pe care il si actualizeaza
    // si o stiva (pe care o construieste, fiind transmisa prin referinta) ce va contine nodurile in ordinea
    // inversa a timpilor de finalizare
    vector<int> topoSort();
    // metoda care - mi returneaza un vector continand nodurile intr-o ordine de sortare topologica
    void DFKosaraju(vector<vector<pair<int, int>>>, vector<vector<int>>&, int, vector<bool>&);
    //  DF util pentru Kosaraju, primeste lista de adiacenta a grafului transpus, lista componentelor conexe pe care o actualizeaza, fiind
    // transmisa prin referinta, nodul de start al DF - ului si vectorul care contine informatii de tip vizitat / nevizitat despre noduri
    // de asemenea transmis prin referinta pentru ca - l modifica
    vector<vector<int>> Kosaraju();
    // algoritmul lui Kosaraju, imi returneaza lista componentelor conexe, adica o lista de liste de noduri
    vector<vector<int>> biconnectedComponents();
    void dfBCC(int, vector<bool>&, vector<int>&, vector<int>&, vector<vector<int>>&, stack<pair<int, int>>&);
    int diameter();
};

Graph::Graph(int _V, int _E, vector<vector<pair<int, int>>> _adj) : V (_V), E(_E), adj(_adj) {
}

void Graph::DFSUtil(int v, vector<bool>& vis, vector<int>& island){
    for(auto i : adj[v]){
        int ngb = i.first;
        if(!(vis[ngb])) {
            island.push_back(ngb);
            vis[ngb] = true;
            DFSUtil(ngb, vis, island);
        }
    }
}
vector<int> Graph::DFS(int src, vector<bool>& vis) {
    // prin "island" returnez 'insula' obtinuta din parcurgerea dfs din nodul curent, adica in principiu
    // nodurile din componenta sa conexa (in grafuri neorientate e mai intuitiv) si in ordinea dfs
    vector<int> island;
    DFSUtil(src, vis, island);
    return island;
}

int Graph::connectedComponents() {
    int nrIslands = 0;
    vector<bool> vis;
    vis.resize(V + 1, false);
    for(int i = 1; i <= V; ++i) {
        if(!vis[i]){
            ++nrIslands;
            DFS(i, vis);
        }
    }
    return nrIslands;
}

// returnez un vector al distantelor minime
// dar si un vector ce contine ordinea parcurgerii bfs
pair<vector<int>, vector<int>> Graph::bfs(int src) {
     pair<vector<int>, vector<int>> toReturn;
     queue<int> q;
     q.push(src);
     vector<int> bfsOrder;
     vector<int> dist;
     dist.resize(V + 1, -1);
     q.push(src);
     dist[src] = 0;
     while(!(q.empty())){
         int dad = q.front();
         bfsOrder.push_back(dad);
         q.pop();
         for(auto i : adj[dad]) {
             int ngb = i.first;
             if(dist[ngb] == - 1){
                  dist[ngb] = dist[dad] + 1;
                  q.push(ngb);
            }
        }
    }
    toReturn.first = dist;
    toReturn.second = bfsOrder;
    return toReturn;
}

void Graph::dfForTopoSort(int src, vector<bool>& vis, stack<int>& st) {
    for(auto i: adj[src]) {
        int ngb = i.first;
        if(vis[ngb] == false) {
            vis[ngb] = true;
            dfForTopoSort(ngb, vis, st);
        }
    }
    st.push(src);
}

vector<int> Graph::topoSort(){
    vector<bool> vis;
    stack<int> st;
    vis.resize(V + 1, false);
    for(int i = 1; i <= V; ++i)
         if(!vis[i]) {
            vis[i] = true;
            dfForTopoSort(i, vis, st);
        }
    vector<int> topoSorted;
    while(st.size()) {
        topoSorted.push_back(st.top());
        st.pop();
    }
    return topoSorted;
}


void Graph::DFKosaraju(vector<vector<pair<int, int>>> adjT, vector<vector<int>>& sol, int node, vector<bool>& visT){
    sol[sol.size() - 1].push_back(node);
    visT[node] = true;
    for(auto i: adjT[node]) {
            int ngb = i.first;
            if(visT[ngb] == false)
            {
                DFKosaraju(adjT, sol, ngb, visT);
            }
        }
}

vector<vector<int>> Graph::Kosaraju() {
    vector<vector<pair<int, int>>> adjT;
    adjT.resize(V + 1);
    for(int i = 1; i <= V; ++i)
        for(auto ngb : adj[i])
            adjT[ngb.first].push_back(make_pair(i, 0));

    vector<bool> visT;
    vector<bool> vis;

    visT.resize(V + 1, false);
    vis.resize(V + 1, false);

    stack<int> st;
    vector<vector<int>> stronglyCC;
    for(int i = 1; i <= V; ++i)
        if(!vis[i])
            {
                vis[i] = true;
                dfForTopoSort(i, vis, st);
                // construim stiva specifica sortarii topologice
                // adica cu nodurile in ordinea inversa a timpilor de finalizare
                // e un pic impropriu sa vorbim despre sortare topologica si componente tare
                // conexe in aceeasi problema deoarece exista unei componente tare conexe
                // implica existenta unui ciclu, si stim ca grafurile care contin cicluri
                // nu admit sortare topologica, dar alegerea nodurilor in ordinea inversa a
                // timpilor de finalizare este valabila pentru ambele probleme

            }

     while(st.size())
        {
            stronglyCC.push_back(vector<int>());
            while(st.size() && visT[st.top()] == true)
                st.pop();
            if(st.size())
            {
                int crt = st.top();
                DFKosaraju(adjT, stronglyCC, crt, visT);
            }
        }
    return stronglyCC;
}


vector<vector<int>> Graph::biconnectedComponents() {
    vector<bool> vis;
    vis.resize(V + 1, false);
    vector<int> level;
    level.resize(V + 1);
    vector<int> minLevel;
    minLevel.resize(V + 1);
    vector<vector<int>> BCC;
    stack<pair<int, int>> edges;
    level[1] = 0;
    dfBCC(1, vis, level, minLevel, BCC, edges);

    return BCC;
}


void Graph::dfBCC(int crt, vector<bool>& vis, vector<int>& level, vector<int>& minLevel, vector<vector<int>>& BCC, stack<pair<int, int>>& edges) {
    vis[crt] = true;
    minLevel[crt] = level[crt];
    for(auto i: adj[crt]) {
        int ngb = i.first;
        if(vis[ngb] == false) {
            level[ngb] = level[crt] + 1;
            edges.push(make_pair(crt, ngb));
            dfBCC(ngb, vis, level, minLevel, BCC, edges);
            if(minLevel[ngb] >= level[crt]) {
                BCC.push_back(vector<int>());
                BCC[BCC.size() - 1].push_back(crt);
                while((edges.top().first == crt && edges.top().second == ngb) == false) {
                    BCC[BCC.size() - 1].push_back(edges.top().second);
                    edges.pop();
                }
                BCC[BCC.size() - 1].push_back(ngb);
                edges.pop();
            }
                minLevel[crt] = min(minLevel[crt], minLevel[ngb]);
        }
        else if (level[crt] - level[ngb] >= 2)
            minLevel[crt] = min(minLevel[crt], level[ngb]);
    }
}


int Graph::diameter() {
    vector<int> dst = (this->bfs(1)).first;
    int maxDist = -1;
    int maxDistVertex = 0;
    for(int i = 1; i <= V; ++i)
        if(dst[i] > maxDist) {
            maxDist = dst[i];
            maxDistVertex = i;
        }
    dst = (this->bfs(maxDistVertex)).first;
    for(int i = 1; i <= V; ++i)
        if(dst[i] > maxDist) {
            maxDist = dst[i];
            maxDistVertex = i;
        }
    return maxDist + 1;
}

int main()
{
    /*
    // problema dfs pe pe infoarena
    // https://www.infoarena.ro/problema/dfs
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int v, e;
    fin >> v >> e;
    vector<vector<pair<int, int>>> adj;
    adj.resize(v + 1);
    Graph g(undirected, unweighted);
    for(int i = 1; i <= e; ++i) {
        int src, dst;
        fin >> src >> dst;
        adj[src].push_back(make_pair(dst, 0));
        adj[dst].push_back(make_pair(src, 0));
    }
    g.build(v, e, adj);
    fout << g.connectedComponents();
    */

    // problema bfs de pe infoarena
    // https://www.infoarena.ro/problema/bfs

    /*
    // problema Sortare topologica de pe infoarena
    // https://www.infoarena.ro/problema/sortaret
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int v, e, start;
    Graph g(directed, unweighted);
    vector<vector<pair<int, int>>> adj;
    fin >> v >> e;
    adj.resize(v + 1);
    for(int i = 1; i <= e; ++i) {
         int src, dst;
         fin >> src >> dst;
         adj[src].push_back(make_pair(dst, 0));
    }
    g.build(v, e, adj);
    vector<int> topoOrder = g.topoSort();
    for(auto v: topoOrder)
        fout << v << ' ';
    fout << '\n';
    */

    /* pentru HavelHakimi, in vectorul 'forHavelHakimi'
    punem secventa de numere despre care vrem sa vedem
    daca poate reprezenta secventa gradelor unui graf
    vector<int> forHavelHakimi = {1, 2, 1};
    cout << HavelHakimi(forHavelHakimi);
    */


    /*
    */

    /*
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int v, e;
    vector<vector<pair<int, int>>> adj;
    fin >> v >> e;
    adj.resize(v + 1);

    for(int i = 1; i <= e; ++i) {
        int src, dst;
        fin >> src >> dst;
        adj[src].push_back(make_pair(dst, 0));
    }
    Graph g(v, e, adj);
    vector<vector<int>> SOL = g.Kosaraju();
    fout << SOL.size() - 1 << '\n';
    for(int i = 0; i < SOL.size(); ++i)
       {
        for(int j = 0; j < SOL[i].size(); ++j)
            fout << SOL[i][j] << ' ';
        fout << '\n';
       }
    */
    /*
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int v, e;
    vector<vector<pair<int, int>>> adj;
    fin >> v >> e;
    adj.resize(v + 5);
    for(int i = 1; i <= e; ++i) {
        int src, dst;
        fin >> src >> dst;
        adj[src].push_back(make_pair(dst, 0));
        adj[dst].push_back(make_pair(src, 0));
    }
    Graph g(v, e, adj);
    vector<vector<int>> SOL = g.biconnectedComponents();
    fout << SOL.size() << '\n';
    for(int i = 0; i < SOL.size(); ++i) {
        for(int j = 0; j < SOL[i].size(); ++j)
            fout << SOL[i][j] << ' ';
        fout << '\n';
    }
    */


    ifstream fin("darb.in");
    ofstream fout("darb.out");

    int v, e; vector<vector<pair<int, int>>> adj;
    fin >> v;
    e = v - 1;
    adj.resize(v + 1);
    for(int i = 1; i <= v - 1; ++i) {
            int src, dst;
            fin >> src >> dst;
            adj[src].push_back(make_pair(dst, 0));
            adj[dst].push_back(make_pair(src, 0));
    }

    Graph g(v, e, adj);
    fout << g.diameter();
    return 0;
}