Pagini recente » Cod sursa (job #2847061) | Cod sursa (job #4917) | Cod sursa (job #2481996) | Cod sursa (job #627965) | Cod sursa (job #2369442)
#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;
}