はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

GRL_5_A Diameter of a Tree

問題
木の直径 | グラフ | Aizu Online Judge

木の直径を求める問題です。
1.任意の点(sとする)から最遠の点(tとする)をdfsで求める
2.tから最遠の点(uとする)をdfsで求める。このとき、tとsの距離が木の直径となる。
アルゴリズムは簡潔なのですが、理由はよくわからんです。とりあえず実装してみました。

#include<stdio.h>
#include<stdlib.h>
#define INF 2100000000
#define LARGE 100000

typedef struct node{
	int cost;
	int flg;
}node;

typedef struct list{
	int id;
	int cost;
	struct list *next;
}list;


node N[LARGE];
list *L[LARGE];
int n;


void Make_AdjList(list* L[],int s,int t,int d){
	list *new=malloc(sizeof(list));
	list **p=&L[s];
	/*card作成*/
	new->id=t;	new->cost=d;  new->next=NULL;
	
	while((*p)!=NULL)p=&((*p)->next);
	(*p)=new;
	
	return;
}


void dfs(int start,int cnt){
	int u=start;
	list *p=L[u];
	
	if(cnt==n)return;
	
	while(p!=NULL){
		if(N[p->id].flg==0){
			N[p->id].cost=N[u].cost+p->cost;
			N[p->id].flg=1;
			cnt++;
			dfs(p->id,cnt);
		}
		p=p->next;
	}
	
	return;
	
}


int main(){
	int i,max,idx;
	int s,t,w;

	
	scanf("%d",&n);
	
	/*初期化*/
	for(i=0;i<n;i++){
		N[i].cost=INF; N[i].flg=0;
		L[i]=NULL;
	}
	N[0].cost=0; N[0].flg=1;
	
	/*隣接リスト作成*/
	while(scanf("%d %d %d",&s,&t,&w)!=EOF){
		Make_AdjList(L,s,t,w);
		Make_AdjList(L,t,s,w);
	}
	
	
	dfs(0,1);
	
	/*0番から最遠点を求める*/
	max=-1;
	for(i=0;i<n;i++){
		if(N[i].cost!=INF && max < N[i].cost){
			max=N[i].cost;
			idx=i;
		}
	}
	
	/*初期化*/
	for(i=0;i<n;i++){
		N[i].cost=INF;  N[i].flg=0;
	}
	N[idx].cost=0; N[idx].flg=1;
	
	dfs(idx,1);
	
	max=-1;
	for(i=0;i<n;i++){
		if(N[i].cost!=INF && max < N[i].cost){
			max=N[i].cost;
			idx=i;
		}
	}
	
	printf("%d\n",max);
	
	return 0;
}

最近は理解できない問題が多く、つらいです。