Cod sursa(job #2437375)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 9 iulie 2019 13:46:19
Problema Diametrul unui arbore Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 200005

typedef struct
{
    int  childCount;
    int  incr;
    int  vecSize;
    int* children;
    int  distance;
} Node;

int n;
Node* graph;

int queue[MAX_QUEUE_SIZE];
int diameter = 0;
int lastOne = 1;

void PushToGraph(int node1, int node2)
{
    graph[node1].childCount++;
    if(graph[node1].childCount > graph[node1].vecSize)
    {
        graph[node1].vecSize += graph[node1].incr;
        graph[node1].incr <<= 1;
        graph[node1].children = (int*)realloc(graph[node1].children, sizeof(int) * graph[node1].vecSize);
    }

    graph[node1].children[graph[node1].childCount - 1] = node2;

}

void BFS(int startingNode)
{
    int queueStart = 0;
    int queueEnd = 0;
    queue[queueEnd++] = startingNode;

    for(int i = 0; i <= n; i++)
        graph[i].distance = 0;

    graph[startingNode].distance = 1;

    while(queueStart != queueEnd)
    {
        int node = queue[queueStart++];
        int distance = graph[node].distance;

        for(int i = 0; i < graph[node].childCount; i++)
        {
            int node2 = graph[node].children[i];
            if(graph[node2].distance == 0)
            {
                int newDist = distance + 1;

                diameter = newDist;
                lastOne = node2;

                queue[queueEnd++] = node2;
                graph[node2].distance = newDist;
            }
        }
    }
}

int main()
{
    FILE* fin = fopen("darb.in", "r");
    FILE* fout = fopen("darb.out", "w");

    fscanf(fin, "%d", &n);

    graph = (Node*)malloc(sizeof(Node) * (n + 1));
    for(int i = 0; i <= n; i++)
    {
        graph[i].childCount = 0;
        graph[i].incr = 1;
        graph[i].vecSize = 0;
        graph[i].children = NULL;
        graph[i].distance = 0;
    }

    for(int i = 0; i < n-1; i++)
    {
        int node1, node2;
        fscanf(fin, "%d %d", &node1, &node2);

        PushToGraph(node1, node2);
        PushToGraph(node2, node1);
    }

    BFS(1);
    BFS(lastOne);

    fprintf(fout, "%d\n", diameter);

// Know it's not good practice, but we must speed up
// the algorithm
/*
    for(int i = 0; i <= n; i++)
        if(graph[i].children)
        {
            free(graph[i].children);
            graph[i].children = NULL;
        }

    free(graph);
    graph = NULL;

    fclose(fout);
    fout = NULL;

    fclose(fin);
    fin = NULL;
*/

    return 0;
}