E_2+?, hQQH 7Q` _2+?#BHBiv BM S2i`B L2ib
9yN
6Q` 2tKTH2- r?2M +QMbi`m+iBM; `2}M2K2Mib 7Q` :oaa G- r?2M p`B#H2
Bb #QmM/2/ #Qp2 #v bQK2 +QMbiMi c- EQb`Dm bm;;2bib iQ ;2M2`i2 `2}M2K2Mib
R i (G) 7Q` 2p2`v i 7`QK {0, . . . , c}X AMbi2/- r2 `2}M2 QMHv iQ R i (G) 7Q` pHm2b i
i?i 72im`2 BM i?2 +Q``2bTQM/BM; b2KBHBM2` b2iX
h?2 H;Q`Bi?K ?b HbQ #22M KmHiBi?`2/2/ rBi? >bF2HHǶb HB;?ir2B;?i +QM@
+m``2M+v iQQHFBi (R)- bQ i?i Bi 2pHmi2b `2}M2K2Mib BM T`HH2H `i?2` i?M b2@
[m2MiBHHvX Mv `2im`M pHm2 Q7 EQb`Dm>QH/b rBHH i2`KBMi2 i?2 T`Q;`KX
h?2 T`Q;`K mb2b i?2 pbb HB#``v U`2H2b2/ b T`i Q7 i?Bb Tm#HB+iBQMV iQ
T`b2 }H2 7Q`KibX "v /27mHi T`b2` 7Q` JAahǶb XbT2+ 7Q`Ki
R Bb T`QpB/2/X
h?Bb 7Q`Ki Bb i`/BiBQMHHv `2T`2b2MiiBQM Q7 +Qp2`#BHBiv T`Q#H2Kbc E_2+?
i`MbHi2b i?2b2 iQ `2+?#BHBiv T`Q#H2Kb #v `2TH+BM; p ≥ n +QMbi`BMib #v p = n
BM i`;2i TH+2bX
j AMbiHHiBQM M/ lb;2
AMbiHHiBQM h?2 E_2+? iQQH Bb pBH#H2 7`QK Tm#HB+ :Bi>m# `2TQbBiQ`vX
PM2 +M +HQM2 i?2 `2TQbBiQ`v BM 7mHH rBi? i?2 7QHHQrBM; +QKKM/,
h?2 T`Q;`K Bb #mBHi ;BMbi i?2 >bF2HH bi+F iQQH+?BM
k X AM Q`/2` iQ #mBH/
i?2 iQQH- HQ+HHv BMbiHH2/ p2`bBQM Q7 bi+F Bb `2[mB`2/X h?2 iQQH +M #2 +QKTBH2/
M/ HQ+HHv BMbiHH2/ #v `mMMBM; bi+F BMbiHH BM i?2 +HQM2/ /B`2+iQ`vX PM2
Kmbi HbQ 2Mbm`2 i?i M aJh bQHp2` Bb BMbiHH2/ M/ ++2bbB#H2 QM i?2 mb2`Ƕb
#BM`v Ti?c xj
j M/ +p+9
9 `2 bmTTQ`i2/X +QKTBH2/ T`Q;`K #BM`v- HQM;
rBi? #2M+?K`Fb- Bb T`QpB/2/ QM i?2 dz_2H2b2bǴ b2+iBQM Q7 i?2 :Bi>m# T;2X
lb;2 h?2 +QKTBH2/ FQb`Dm iQQH +M #2 BMi2`+i2/ rBi? i?`Qm;? i?2 +QK@
KM/ HBM2X aBKTH2 r`TT2` b+`BTib `2 T`QpB/2/c i?2 biM/`/ BMpQ+iBQM Bb
F`2+? 6AG1LJ1 iQ +?2+F `2+?#BHBiv- M/ F+Qp2` 6AG1LJ1 7Q` +Qp2`#BHBivX
AMi2`K2/Bi2 QmiTmi +M #2 ?B//2M #v T`QpB/BM; i?2 @[ U[mB2iV ~;X
6B;m`2 j# b?Qrb i?2 `2HiBp2 T2`7Q`KM+2 Q7 xj ;BMbi +p+9 7Q` ;`QrBM;
BMTmibX +p+9 i2M/b iQ 7` QmiT2`7Q`K xj QM i?2 +QMbi`m+i2/ AGS T`Q#H2KbX
9 1tT2`BK2MiH _2bmHib
E*Qp2` HHQrb mb iQ mb2 #2M+?K`Fb 7Q` i?2 +Qp2`#BHBiv T`Q#H2K b bQm`+2
Q7 i2bi +b2b 7Q` i?2 `2+?#BHBiv H;Q`Bi?KX h?2 bmBi2 T`QpB/2/ rBi? i?2 iQQH
BM+Hm/2b HbQ MmK#2` Q7 i2bi +b2b 7Q` p`BQmb bT2+ib Q7 i?2 BKTH2K2MiiBQMb r2HH b 2tKTH2b 7`QK i?2 MQM@2H2K2Mi`v HQr2` #QmM/ +QMbi`m+iBQM (d)X
E_2+? rb 2pHmi2/ ;BMbi KMv T`Q#H2Kb M/ bQHp2`b 7`QK i?2 HBi2`im`2
QM +Qp2`#BHBivX Z*Qp2` (9) BKTH2K2Mib +Qp2`#BHBiv #b2/ QM `2HtiBQM iQ +QM@
iBMmQmb +Qp2`#BHBivc A*Qp2` (RR) `2}M2b i?Bb 7m`i?2` rBi? BM/m+iBp2 BMp`BMibX
R ?iiTb,ff;Bi?m#X+QKfTB2``2;MivfKBbifrBFB
k ?iiTb,ff/Q+bX?bF2HHbi+FXQ`;f2Mfbi#H2f_1.J1f
j ?iiTb,ff;Bi?m#X+QKfwjS`Qp2`fxj
9 ?iiTb,ff+p+9X;Bi?m#XBQ
git clone https://github.com/dixonary/kosaraju.git
9yN
6Q` 2tKTH2- r?2M +QMbi`m+iBM; `2}M2K2Mib 7Q` :oaa G- r?2M p`B#H2
Bb #QmM/2/ #Qp2 #v bQK2 +QMbiMi c- EQb`Dm bm;;2bib iQ ;2M2`i2 `2}M2K2Mib
R i (G) 7Q` 2p2`v i 7`QK {0, . . . , c}X AMbi2/- r2 `2}M2 QMHv iQ R i (G) 7Q` pHm2b i
i?i 72im`2 BM i?2 +Q``2bTQM/BM; b2KBHBM2` b2iX
h?2 H;Q`Bi?K ?b HbQ #22M KmHiBi?`2/2/ rBi? >bF2HHǶb HB;?ir2B;?i +QM@
+m``2M+v iQQHFBi (R)- bQ i?i Bi 2pHmi2b `2}M2K2Mib BM T`HH2H `i?2` i?M b2@
[m2MiBHHvX Mv `2im`M pHm2 Q7 EQb`Dm>QH/b rBHH i2`KBMi2 i?2 T`Q;`KX
h?2 T`Q;`K mb2b i?2 pbb HB#``v U`2H2b2/ b T`i Q7 i?Bb Tm#HB+iBQMV iQ
T`b2 }H2 7Q`KibX "v /27mHi T`b2` 7Q` JAahǶb XbT2+ 7Q`Ki
R Bb T`QpB/2/X
h?Bb 7Q`Ki Bb i`/BiBQMHHv `2T`2b2MiiBQM Q7 +Qp2`#BHBiv T`Q#H2Kbc E_2+?
i`MbHi2b i?2b2 iQ `2+?#BHBiv T`Q#H2Kb #v `2TH+BM; p ≥ n +QMbi`BMib #v p = n
BM i`;2i TH+2bX
j AMbiHHiBQM M/ lb;2
AMbiHHiBQM h?2 E_2+? iQQH Bb pBH#H2 7`QK Tm#HB+ :Bi>m# `2TQbBiQ`vX
PM2 +M +HQM2 i?2 `2TQbBiQ`v BM 7mHH rBi? i?2 7QHHQrBM; +QKKM/,
h?2 T`Q;`K Bb #mBHi ;BMbi i?2 >bF2HH bi+F iQQH+?BM
k X AM Q`/2` iQ #mBH/
i?2 iQQH- HQ+HHv BMbiHH2/ p2`bBQM Q7 bi+F Bb `2[mB`2/X h?2 iQQH +M #2 +QKTBH2/
M/ HQ+HHv BMbiHH2/ #v `mMMBM; bi+F BMbiHH BM i?2 +HQM2/ /B`2+iQ`vX PM2
Kmbi HbQ 2Mbm`2 i?i M aJh bQHp2` Bb BMbiHH2/ M/ ++2bbB#H2 QM i?2 mb2`Ƕb
#BM`v Ti?c xj
j M/ +p+9
9 `2 bmTTQ`i2/X +QKTBH2/ T`Q;`K #BM`v- HQM;
rBi? #2M+?K`Fb- Bb T`QpB/2/ QM i?2 dz_2H2b2bǴ b2+iBQM Q7 i?2 :Bi>m# T;2X
lb;2 h?2 +QKTBH2/ FQb`Dm iQQH +M #2 BMi2`+i2/ rBi? i?`Qm;? i?2 +QK@
KM/ HBM2X aBKTH2 r`TT2` b+`BTib `2 T`QpB/2/c i?2 biM/`/ BMpQ+iBQM Bb
F`2+? 6AG1LJ1 iQ +?2+F `2+?#BHBiv- M/ F+Qp2` 6AG1LJ1 7Q` +Qp2`#BHBivX
AMi2`K2/Bi2 QmiTmi +M #2 ?B//2M #v T`QpB/BM; i?2 @[ U[mB2iV ~;X
6B;m`2 j# b?Qrb i?2 `2HiBp2 T2`7Q`KM+2 Q7 xj ;BMbi +p+9 7Q` ;`QrBM;
BMTmibX +p+9 i2M/b iQ 7` QmiT2`7Q`K xj QM i?2 +QMbi`m+i2/ AGS T`Q#H2KbX
9 1tT2`BK2MiH _2bmHib
E*Qp2` HHQrb mb iQ mb2 #2M+?K`Fb 7Q` i?2 +Qp2`#BHBiv T`Q#H2K b bQm`+2
Q7 i2bi +b2b 7Q` i?2 `2+?#BHBiv H;Q`Bi?KX h?2 bmBi2 T`QpB/2/ rBi? i?2 iQQH
BM+Hm/2b HbQ MmK#2` Q7 i2bi +b2b 7Q` p`BQmb bT2+ib Q7 i?2 BKTH2K2MiiBQMb r2HH b 2tKTH2b 7`QK i?2 MQM@2H2K2Mi`v HQr2` #QmM/ +QMbi`m+iBQM (d)X
E_2+? rb 2pHmi2/ ;BMbi KMv T`Q#H2Kb M/ bQHp2`b 7`QK i?2 HBi2`im`2
QM +Qp2`#BHBivX Z*Qp2` (9) BKTH2K2Mib +Qp2`#BHBiv #b2/ QM `2HtiBQM iQ +QM@
iBMmQmb +Qp2`#BHBivc A*Qp2` (RR) `2}M2b i?Bb 7m`i?2` rBi? BM/m+iBp2 BMp`BMibX
R ?iiTb,ff;Bi?m#X+QKfTB2``2;MivfKBbifrBFB
k ?iiTb,ff/Q+bX?bF2HHbi+FXQ`;f2Mfbi#H2f_1.J1f
j ?iiTb,ff;Bi?m#X+QKfwjS`Qp2`fxj
9 ?iiTb,ff+p+9X;Bi?m#XBQ
git clone https://github.com/dixonary/kosaraju.git