$B1i=,LdBj!!Bh(B6$B2s!!%0%i%U$NC5:w(B($B=d2s(B): $B2#7?C5:w(B(2017$B!"(B2019$BG/EY(B)

$B"#(B $B3X@RHV9f$K$h$kLdBj@_Dj(B
$B!&3X@RHV9f$N:G2<0L7e$NCM$K$h$C$F;XDj$5$l$?LdBj$r3F<+$N1i=,LdBj$H$7$^$9(B
$B"!A0H>$N%0%k!<%W(B
$B!!!!!!HV9f!!D:E@?t!!3+;O(B
$B!!!!!!!!!!!!!!!!!!!!!!!!D:E@(B
$B!!!!(B0: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($BElF|K\(B)$B$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B1: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($BElF|K\(B)$B$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B2: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($B@>F|K\(B)$B$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B3: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($B@>F|K\(B)$B$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B4: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($B?@F`@n8)(B)$B$N%P%9Dd!"JU(B: $B%P%9O)@~(B
$B!!!!(B5: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb(B($B?@F`@n8)(B)$B$N%P%9Dd!"JU(B: $B%P%9O)@~(B
$B!!!!(B6: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B7: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B8: $B!!(B6a$B!"!!(B10$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb$N9AOQET;TL>!"JU(B: $B9RO)(B
$B!!!!(B9: $B!!(B6a$B!"!!(B10$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BF|K\9qFb$N9AOQET;TL>!"JU(B: $B9RO)(B
$B"!8eH>$N%0%k!<%W(B
$B!!!!!!HV9f!!D:E@?t!!3+;O(B
$B!!!!!!!!!!!!!!!!!!!!!!!!D:E@(B
$B!!!!(B0: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $B%h!<%m%C%Q$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B1: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $B%h!<%m%C%Q$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B2: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $BKL%"%a%j%+$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B3: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $BKL%"%a%j%+$N1XL>!"JU(B: $BE4F;O)@~(B
$B!!!!(B4: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $B%"%U%j%+$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B5: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $B%"%U%j%+$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B6: $B!!(B6a$B!"!!(B12$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $B%h!<%m%C%Q$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B7: $B!!(B6a$B!"!!(B12$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $B%h!<%m%C%Q$N6u9AET;TL>!"JU(B: $B9R6uO)@~(B
$B!!!!(B8: $B!!(B6a$B!"!!(B10$B!!!!(B1$B!!!!!!!!!!!!D:E@(B: $B%"%8%"$N9AOQET;TL>!"JU(B: $B9RO)(B
$B!!!!(B9: $B!!(B6a$B!"!!(B10$B!!!!(B2$B!!!!!!!!!!!!D:E@(B: $B%"%8%"$N9AOQET;TL>!"JU(B: $B9RO)(B
$B!&A4$F$ND:E@$K$D$$$F!"(B$B
$B!&9RO)$K$D$$$F$O!"N95R!?2_J*!"8BDj$O$7$^$;$s!#(B $B!&8m$C$?LdBjHV9f!"8m$C$?@_DjCM$G%l%]!<%H$rDs=P!"$^$?J#?t$NLdBj$KBP$7$F%l%]!<%HDs=P$O



6a $BL58~%0%i%UC5:w$N1~MQ(B
$B!!(B $B8=l9g!"A0$,D:E@!"!"JU$,(B $B9RO)$KAjEv$9$k%0%i%U$H$7$FI=8=$G$-$k!#(B
$B!!(B $B>e5-$NLdBj@_Dj$K4p$E$-!"8!:w%(%s%8%s$G(B)$B$G%0%i%U$r:n@.$9$k!#$=$N:]!"%0%i%U$ND:E@$K$O!"D:E@HV9f$@$1$G$J$/!"1XL>$^$?$OET;TL>$r5-=R$9$k!#$3$N%0%i%U(B($B2hA|(B)$B$r!"%l%]!<%H$K$O$j$D$1$k(B(MS WORD$B%U%!%$%k$K2hA|$rA^F~$9$k(B)$B!#Ev3:%0%i%U$KBP$9$kNY@\%j%9%H(B($B%"%k%4%j%:%`O@-5Bh(B13$B2s;2>H(B)$B$r@8@.$9$k$?$a$N%G!<%?$r!"%U%!%$%k$G$OL5$/%W%m%0%i%`$NCf$G@0?tCM$NFs $B!!!!!!(Bint graph_array[5][5] = {
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B{4, , , ,},
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B{1, 3, 2, 3, 4},
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B{2, 2, 1, 4, ,},
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B{3, 2, 1, 4, ,},
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B{4, 3, 1, 2, 3},
$B!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!(B} ;
$B!!=PH/D:E@$K$D$$$F$b!"JQ?t$KBeF~$9$k!#(B
$B!!%U%!%$%k$G$O$J$/>e5-$NG[Ns$+$iNY@\%j%9%H$r@8@.$G$-$k$h$&$K(B6.4$B@a0J2<$K5-=R$5$l$F$$$k%W%m%0%i%`$rJQ99$7!"2<5-$N(B2$B$D$NA`:n$r $B!!(B(a) $B>e5-G[Ns$ND:E@HV9f$H$=$ND:E@L>(B($BET;TL>!"%P%9DdL>!"1XL>(B)$B$r=PNO$9$k(B
$B!!(B(b) $B=D7?C5:w(B($B$@$1(B)
$B%l%]!<%H$K$O(B13$B%Z!<%8$N=PNO2hLL$K<($5$l$k$h$&$J!"K,Ld$7$?=g$KD:E@HV9f$N%j%9%H$r7G:\$7!"Ev3:2]Bj$KBP$7MM!9$J4QE@$+$i9M;!$;$h!#(B
$B!!%W%m%0%i%_%s%05;=Q$rM-$7!"Ev3:%"%k%4%j%:%`$r$h$/M}2r$7$F$$$ke$HF1MM$KG[Ns$K3JG<$7!"=D7?C5:w%W%m%0%i%`$r


$BK\G/EY(B(2019)$B$O0J2<$NA*Br2]Bj$O2]$7$^$;$s!#(B
6b $BD:E@%*%V%8%'%/%H$NDI2C$H=D7?C5:w(B($B=d2s(B)$B$N3HD%(B
$B!!%0%i%UM}O@$G$O!"D:E@!"JU$OC1$KHV9f$G<1JL$5$l$k$@$1$G$"$k$,!"8=l9g!"D:E@$KHV9f(B($BD:E@<1JL;R(B)$B$@$1$G$J$/!"%*%V%8%'%/%H$r;}$?$;$k$3$H$G$h$j8= $B!!(B typedef struct obj {$B!!!!!!!!(B //
$B!!!!!!!!(Bchar *city ;$B!!!!!!!!!!!!(B // $BET;TL>(B
$B!!(B} OBJECT ;

$B!!(Btypedef struct node { $B!!!!!!(B// $BD:E@@a(B
$B!!!!!!(Bint vn ; $B!!!!!!!!!!!!!!!!!!!!(B// $BD:E@HV9f(B
$B!!!!!!(B OBJECT obj ; $B!!!!!!!!!!(B//
$B!!!!!!(B struct node *next ; $B!!!!(B// $B8eB3@a(B($BNY@\D:E@(B)$B$X$N%]%$%s%?(B
$B!!(B} NODE ;

$B!!(B6a$B$NLdBj$r3HD%$7!">e5-$N9=B$BN$r;HMQ$7!"$^$?%F%-%9%H(B8$B%Z!<%8$N=D7?C5:w4X?t(B(depth_first)$B$G!"D:E@$NC5:w(B($B=d2s(B)$B;~$KET;TL>$r=PNO$9$k%9%F!<%H%a%s%H$rDI2C$9$k$3$H$G!"=d2s4X?t$NF0:n(B($B=d2s=g=x(B)$B$r$h$j6qBNE*$KM}2r$G$-$k$3$H$,2DG=$H$J$k!#(B
$B!!>e5-$N9=B$BN$*$h$S=D7?C5:w4X?t$r



$B"!(B$B1i=,LdBj%W%m%0%i%`:n@.$K$*$1$kCm0U;v9`(B

$B2<5-$NMW7o$rI,$:K~$?$9$h$&$K(B$B%W%m%0%i%`$r:n@.$;$h!#(B

$B!!(B(1) $B:G=i$KFI$_9~$`%U%!%$%kL>$O@dBP%Q%9$H$7$F(Bmain$B%W%m%0%i%`Cf$G5-=R$7(B$B!"%3%^%s%I%i%$%s>e$N0z?t$K$h$k;XDj!"$*$h$S%j%@%$%l%/%H$K$h$kF~NO;XDj$O$7$J$$$3$H!#(B

$B!!!!!!Nc(B. char infile[80] = "/home/algorithm_data/texte.dat" ;

$B!!(B(2) $BHf3S2s?t!"$BB,Dj7k2L$r%W%m%0%i%`$N:G8e$K=PNO(B$B$9$k!#(B