Cod sursa(job #2190670)

Utilizator ibogdan25Ilie Ionut ibogdan25 Data 31 martie 2018 14:46:51
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stdio.h>

#define INF 0x7fffffff
#define NMAX 100002

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
struct Nod {
    int nod;
    int distanta;
    bool operator<(const Nod &o) const
    {
        return distanta > o.distanta;
    }

};
vector < vector < int > > G(NMAX);
vector < int > dist(NMAX, 0);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m, s;

bool compare (const Nod& a, const Nod& b) {
    return a.distanta < b.distanta;
}

void read() {
    FILE * pFile;

    pFile = fopen("darb.in", "r");
    //f >> n >> m;
    fscanf(pFile, "%d", &m);
    int x = 0, y = 0, dist = 0;
    Nod nod_pereche;
    while (m--) {
        fscanf(pFile, "%d %d", &x, &y);
        if (x > n) {
            n = x;
        }
        if (y > n) {
            n = y;
        }
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
Nod constructNode(int nod, int distanta) {
    Nod new_node;
    new_node.nod = nod;
    new_node.distanta = distanta;
    return new_node;
}
void bfs(int nod_sursa) {
    queue<int> qNode;
    qNode.push(nod_sursa);
    vizitat[nod_sursa] = true;
    while (!qNode.empty()) {
        int nod = qNode.front();
        qNode.pop();
        for (int i = 0; i < G[nod].size(); i++) {
            int nodVecin = G[nod][i];
            if (!vizitat[nodVecin]) {
                vizitat[nodVecin] = true;
                dist[nodVecin] = dist[nod] + 1;
                qNode.push(nodVecin);
            }
        }
    }
    /*FILE * pFile;

    pFile = fopen("bfs.out", "w");
    for (int i = 1; i <= n; i++) {
        if (!dist[i] && i != s) {
            dist[i] = -1;
        }
        fprintf(pFile, "%d ", dist[i]);
    }*/
}
int main()
{
    read();
    bfs(1);
    dist.clear();
    vizitat.clear();
    int maxim = -1, nodMax = 0;
    for (int i = 2; i <= n; i++){
        if (dist[i] > maxim) {
            maxim = dist[i];
            nodMax = i;
        }
    }
    for (int i = 0; i <= NMAX; i++) {
        dist.push_back(0);
        vizitat.push_back(false);
    }
    bfs(nodMax);
    maxim = -1, nodMax = 0;
    for (int i = 2; i <= n; i++){
        if (dist[i] > maxim) {
            maxim = dist[i];
            nodMax = i;
        }
    }
    g << maxim + 1;
    return 0;

}