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; }
最近は理解できない問題が多く、つらいです。