Pagini recente » Cod sursa (job #636293) | Cod sursa (job #379353) | Cod sursa (job #28099) | Cod sursa (job #2633317) | Cod sursa (job #2437375)
#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;
}