# -*- coding: utf-8 -*-


def makeAdjAndAdjT(arr, n):
    adj = [[] for i in range(n)]
    adjT = [[] for i in range(n)]
    for i in arr:
        adj[i[0]].append(i[1])
        adjT[i[1]].append(i[0])
    return [sorted(i) for i in adj], [sorted(i) for i in adjT]


def myDfs(adj, n):
    arr = []
    used = [False for i in range(n)]
    stackDfs = []

    while stackDfs or (False in used):
        if not stackDfs:
            for i in range(len(used)):
                if not used[i]:
                    stackDfs.append(i)
                    used[i] = True
                    break

        deadlock = True
        for v in adj[stackDfs[-1]]:
            if not used[v]:
                stackDfs.append(v)
                used[v] = True
                deadlock = False
                break

        if deadlock:
            arr.append(stackDfs.pop())
    return arr


def getComponents(adjT, stepOne):
    stepOne.reverse()
    componentsArr = [-1 for i in range(len(stepOne))]
    used = [False for i in range(n)]
    stack = []
    color = 0

    while stack or (False in used):
        if not stack:
            color += 1
            for i in stepOne:
                if not used[i]:
                    stack.append(i)
                    componentsArr[i] = color
                    used[i] = True
                    break

        deadlock = True
        for v in adjT[stack[-1]]:
            if not used[v]:
                stack.append(v)
                used[v] = True
                componentsArr[v] = color
                deadlock = False
                break

        if deadlock:
            stack.pop()
    return componentsArr


if __name__ == '__main__':
    # Алгоритм Косарайю
    n = 6
    arr = [[0, 1], [0, 4], [1, 0], [1, 2], [2, 3], [2, 5], [4, 1], [5, 3], [5, 4]]
    adj, adjT = makeAdjAndAdjT(arr, n)

    stepOne = myDfs(adj, n)

    colors = getComponents(adjT, stepOne)
    components = [[] for i in range(max(colors))]
    for i, item in enumerate(colors):
        components[item-1].append(i)

    print("Компоненты сильной связности:")

    for i in components:
        print(i)