Cod sursa(job #2369442)

Utilizator stratonedanielDaniel Stratone stratonedaniel Data 5 martie 2019 23:18:36
Problema Diametrul unui arbore Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct my_struct
{
	int number_of_neighbors;
	int *neighbors;
}AdjacencyList;

void DFS(AdjacencyList *adjlist, int father,int node, int level, int *maxlevel, int *maxnode)
{
	if(adjlist[node].number_of_neighbors == 0)
		return;

	if(level>(*maxlevel))
	{
		(*maxlevel)=level;
		(*maxnode)=node;
	}

	for(int i=0;i<adjlist[node].number_of_neighbors;i++)
	{
		if(father!=adjlist[node].neighbors[i])
			DFS(adjlist,node,adjlist[node].neighbors[i],level+1,maxlevel,maxnode);
	}

}

int main(int argc, char const *argv[])
{
	FILE *read = fopen("darb.in","r");
	FILE *write = fopen("darb.out","w");

	int number_of_vertices;

	fscanf(read, "%d", &number_of_vertices);

	AdjacencyList* adjlist=(AdjacencyList*)calloc(number_of_vertices+1, sizeof(AdjacencyList));

	int x,y;
	int startnode=-1;

	for(int i=0;i<number_of_vertices-1;i++)
	{
		fscanf(read,"%d%d",&x,&y);

		if(startnode==-1)
			startnode=x;

		if(adjlist[x].number_of_neighbors==0)
		{
			adjlist[x].number_of_neighbors++;

			adjlist[x].neighbors=(int*)calloc(adjlist[x].number_of_neighbors,sizeof(int));
			adjlist[x].neighbors[adjlist[x].number_of_neighbors-1]=y;

		}
		else if(adjlist[x].number_of_neighbors!=0)
		{
			adjlist[x].number_of_neighbors++;

			adjlist[x].neighbors=(int*)realloc(adjlist[x].neighbors,adjlist[x].number_of_neighbors*sizeof(int));
			adjlist[x].neighbors[adjlist[x].number_of_neighbors-1]=y;

		}

		if(adjlist[y].number_of_neighbors==0)
		{
			adjlist[y].number_of_neighbors++;

			adjlist[y].neighbors=(int*)calloc(adjlist[y].number_of_neighbors,sizeof(int));
			adjlist[y].neighbors[adjlist[y].number_of_neighbors-1]=x;

		}
		else if(adjlist[y].number_of_neighbors!=0)
		{
			adjlist[y].number_of_neighbors++;

			adjlist[y].neighbors=(int*)realloc(adjlist[y].neighbors,adjlist[y].number_of_neighbors*sizeof(int));
			adjlist[y].neighbors[adjlist[y].number_of_neighbors-1]=x;

		}

	}

	int maxnode=-1;
	int maxlevel=-1;

	DFS(adjlist,-1,1,0,&maxlevel,&maxnode);

	int maxlevel1=-1;
	int maxnode1=-1;

	DFS(adjlist,-1,maxnode,0,&maxlevel1,&maxnode1);

	fprintf(write,"%d\n",maxlevel1+1);

	for(int i=1;i<=number_of_vertices;i++)
		if(adjlist[i].number_of_neighbors!=0)
			free(adjlist[i].neighbors);

	free(adjlist);	

	fclose(read);
	fclose(write);

	return 0;
}