from collections import deque
import random
class Graph:
    """Trida Graph drzi graf reprezentovany matici sousednosti.
    Atributy:
        size: velikost (pocet vrcholu) grafu
        matrix: matice sousednosti
                [u][v] reprezentuje hranu u -> v
    """

    def __init__(self, size):
        self.size = size
        self.matrix = [[False] * size for _ in range(size)]
        self.color =  ['w'] * size
        self.stack = []
        self.label = [None]*size




def Transpose(graph):
    rev_graph = Graph(graph.size)

    for i in range(graph.size):
        for j in range(graph.size):
            rev_graph.matrix[i][j] = graph.matrix[j][i]
    return rev_graph

def push_DFS(graph,u):
    graph.color[u] = 'g'
    for i in range(graph.size):
        if graph.matrix[u][i] == True:
            if graph.color[i] == 'w':
                push_DFS(graph,i)
    graph.color[u] = 'b'
    graph.stack.append(u)

def label_DFS(graph,u,count):
    graph.color[u] = 'g'
    for i in range(graph.size):
        if graph.matrix[u][i] == True:
            if graph.color[i] == 'w':
                label_DFS(graph,i,count)
    graph.color[u] = 'b'
    graph.label[u] = count




def kosaraju_sharir(graph):

    for i in range(graph.size):
        if graph.color[i] == 'w':
            push_DFS(graph,i)
    count = 0

    rev_graph = Transpose(graph)
    graph.color = ['w'] * graph.size
    while graph.stack:
        u = graph.stack.pop()
        if rev_graph.color[u] == 'w':
            count += 1
            label_DFS(rev_graph,u,count)


    print(rev_graph.label)
    ret = {}
    for i in range(len(rev_graph.label)):
        ret.setdefault(rev_graph.label[i],[])
        ret[rev_graph.label[i]].append(i)
    return list(ret.values())



g = Graph(4)
g.matrix = [[1, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 0, 0],
[1, 1, 0, 1]]
print(kosaraju_sharir(g))


def test_generated_strong_compo():
    d = 0
    while d < 1:
        # Generate random graph
        test_int = 4
        test_graph = Graph(test_int)
        test_matrix = []
        for i in range(test_int):
            test_matrix.append([])
            for j in range(test_int):
                if random.randint(0, 1) == 0:
                    test_matrix[i].append(0)
                else:
                    test_matrix[i].append(1)
        test_graph.matrix = test_matrix

        # Compute strong components
        components = kosaraju_sharir(test_graph)
        if len(components) == 4:
            continue

        # Print out its matrix
        print("Graph no." + str(d + 1))
        for i in range(test_int):
            print(test_matrix[i])

        # Print out its strong components
        print("Strong components no." + str(d + 1))
        for j in range(len(components)):
            print(components[j])

        d += 1


test_generated_strong_compo()