Вершини розглядаються у зворотному топологічному порядку, тому в кінці рекурсивної функції для початкової вершини не зустрінеться жодна вершина з тієї ж сильної компоненти, оскільки всі вершини, досяжні з початкової, вже опрацьовано.
Зворотні зв'язки в дереві дають інший шлях з однієї вершини в іншу і зв'язують сильні компоненти.
Алгоритм Тар'яна можна розуміти як варіацію алгоритму пошуку в глибину, в якому під час відвідування вершини і при закінченні опрацювання вершини виконуються додаткові дії. Відвідування вершини відбувається при русі від кореня до листя, а закінчення обробки вершини — на зворотному шляху. Під час відвідування вершини вона проштовхується в допоміжний стек, а виштовхується звідти при закінченні опрацювання[1].
Індекси компонент зв'язності всіх вершин зберігаються у векторі id, індексованому номерами вершин. Вектор low відстежує вершину з найменшим номером у прямому порядку обходу, досяжну з кожного вузла через послідовність прямих зв'язків, за якими слідує один висхідний зв'язок. Скориставшись пошуком у глибину з тим, щоб розглядати вершини в зворотному топологічному порядку, для кожної вершини v обчислюється максимальна точка, досяжна через зворотний зв'язок із попередника (low[v]). Коли для вершини v виконується pre[v]=low[v], вона виштовхується зі стека, а також всі вершини вище від неї і всім їм присвоюється номер компоненти[джерело?].
Час роботи
Алгоритм має часову складність , де — кількість ребер, а — кількість вершин графу[1].
Простова складність становить , бо стек може вирости не більш ніж до (коли граф це одна велика компонента). Також ми зберігаємо додаткові ознаки для вершин.
Алгоритм у псевдокоді
алгоритм Тар'яна цевхід: граф G = (V, E)
вихід: множина компонент сильної зв'язності (множини вершин)
index := 0
S := порожній стек
для кожногоvзVзробитиякщоv.index невизначений тоді
сильнозв'язна(v)
функція сильнозв'язна(v)
// Встановити індекс глибини для v у найменший незайнятий індексv.index := indexv.lowlink := indexindex := index + 1
S.push(v)
v.onStack := істина
// Наступниці vдля кожного (v, w) зEзробитиякщоw.index невизначений тоді// Цю наступницю w ше не відвідували; запускаємо рекурсію на ній
сильнозв'язна(w)
v.lowlink := min(v.lowlink, w.lowlink)
інакше, якщоw.onStack тоді// Наступниця w на стеку S і, значить, в поточній КСЗ// якщо w не на стеку, тоді (v, w) це ребро, що вказує на вже знайдену КСЗ і ми їм нехтуємо// Примітка: Наступний рядок може виглядати дивним, але він правильний.// Він використовує w.index, а не w.lowlink; це навмисно і було в оригінальній статтіv.lowlink := min(v.lowlink, w.index)
// Якщо v це корінь, то виштовхнути зі стеку і породити КСЗякщоv.lowlink = v.index тоді
розпочати нову компоненту сильної зв'язності
повторюватиw := S.pop()
w.onStack := хиба
додати w до поточної компоненти сильної зв'язності
допокиw ≠ v
вивести поточну компоненту сильної зв'язності
Змінна index це лічильник порядку вершини в обході в глибину. S це стек вершин, який напочатку порожній і зберігає історію досліджених вершин, які ще не були записані до якоїсь КСЗ. Зауважте, що це не звичаний стек пошуку в глибину, бо ми не виштовхуємо вершини з нього коли повертаємось вгору деревом, ми виштовхуємо їх лише коли повна компонента сильної зв'язності була знайдена.
Коли кожна вершина завершує рекурсію, якщо її lowlink все ще рівний її index, тоді це корінь компоненти сильної зв'язності, утвореної всіма вершинами вище в стеку. Алгоритм виштовхує зі стеку все вище цієї вершини і її саму записуючи всі ці вершини в нову компоненту.
Tarjan R. E. Depth-first search and linear graph algorithms // SIAM Journal on Computing. — 1972. — Vol. 1, no. 2 (13 July). — P. 146–160. — DOI:10.1137/0201010.