def tarjan_algorithm_with_start(graph: dict[int, set[int]], start_node: int):
    def dfs(v):
        nonlocal index
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for neighbor in graph[v]:
            if indices[neighbor] == -1:
                dfs(neighbor)
                lowlink[v] = min(lowlink[v], lowlink[neighbor])
            elif on_stack[neighbor]:
                lowlink[v] = min(lowlink[v], indices[neighbor])

        if indices[v] == lowlink[v]:
            scc = []
            while True:
                node = stack.pop()
                on_stack[node] = False
                scc.append(node)
                if node == v:
                    break
            strongly_connected_components.append(scc)

    index = 0
    stack = []
    indices = [-1] * len(graph)
    lowlink = [-1] * len(graph)
    on_stack = [False] * len(graph)
    strongly_connected_components = []

    dfs(start_node)

    return strongly_connected_components

import itertools
import numpy as np
from numpy.typing import NDArray

from tarjan.utils import tarjan_algorithm_with_start, matr2dct, colorGraph


class MinimalSubsetDetector:
    def __init__(self, matrix: NDArray, omitOnes: bool = True):
        assert matrix.shape[0] == matrix.shape[1], 'Матрица должна быть квадратной'
        permuted = MinimalSubsetDetector.permuteMatrix(matrix)
        if permuted is None:
            raise ValueError('У переданной матрицы не существует такой перестановки строк, что на главной диагонали стоят единицы.')
        self.matrix = permuted
        self.size = self.matrix.shape[0]
        self.hasRoot = False
        if omitOnes:
            for i in range(self.size):
                self.matrix[i][i] = 0

    @staticmethod
    def permuteMatrix(matrix) -> NDArray | None:
        """
        Находит такую перестановку строк, что на главной диагонали должны стоять только 1.
        O(k^N), где k - примерное кол-во 1 в строке.
        :param matrix:
        :return:
        """
        result = []
        for row in matrix:
            indices = np.where(row == 1)[0]
            result.append(indices.tolist())
        result_dict = {}
        for i, sublist in enumerate(result):
            for element in sublist:
                if element not in result_dict:
                    result_dict[element] = [i]
                else:
                    result_dict[element].append(i)
        result_list = [result_dict.get(i, []) for i in range(len(result))]
        combinations = itertools.product(*result_list)
        valid_perm = next(comb for comb in combinations if len(set(comb)) == len(comb))
        if valid_perm is None:
            print('Такой перестановки не существует.')
            return
        print(f'Необходимая перестановка: {valid_perm}.')
        return matrix[list(valid_perm)]

    @classmethod
    def initfromTeX(cls, dimension: int, texcode: str, omitOnes: bool = True):
        """
        :param omitOnes: опустить единицы на главной диагонали матрицы (убрать петли).
        :param dimension: размерность матрицы
        :param texcode: код для матрицы
        :return:
        """
        tex_matrix = texcode.replace("\\", '&').replace("\n", "")
        elements = tex_matrix.split("&")
        int_elements = [int(element.strip()) for element in elements if len(element)]
        return cls(np.array(int_elements).reshape(dimension, dimension), omitOnes=omitOnes)

    def addRootNode(self, interested_nodes: list[int]):
        """
        Добавление корневой вершины R, которая связана ребрами с interested_nodes. Применяется, когда
        нужно узнать минимальный набор уравнений для нахождения группы неизвестных.
        :param interested_nodes:
        :return:
        """
        self.hasRoot = True
        row = [0] * self.size
        for n in interested_nodes:
            row[n] = 1
        new_row = np.array(row)
        extended_matrix = np.vstack([self.matrix, new_row])
        new_column = np.array([0] * (self.size + 1))
        new_column = new_column[:, np.newaxis]
        self.matrix = np.hstack((extended_matrix, new_column))

    def find(self, node: int = None):
        if node is None and not self.hasRoot:
            raise ValueError('Укажите индекс переменной, которую вы хотите найти.')
        return tarjan_algorithm_with_start(matr2dct(self.matrix), start_node=self.size if self.hasRoot else node)

    def color_SCC(self, scc):
        return colorGraph(self.matrix, scc)


def test1():
    detector = MinimalSubsetDetector.initfromTeX(
        8,
        r'1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\'
        r'1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\'
        r'0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\'
        r'1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\'
        r'0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\'
        r'1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\'
        r'1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\'
        r'0 & 0 & 1 & 0 & 0 & 0 & 0 & 1'
    )
    # Для поиска минимального набора уравнений для переменных у1 и у2.
    # detector.addRootNode([6, 7])
    answers = detector.find(6)  # найти для у1
    print(answers)
    detector.color_SCC(answers)


if __name__ == '__main__':
    test1()

import networkx as nx
import numpy as np
from matplotlib import pyplot as plt


def matr2dct(m):
    gr = {}
    num_nodes = m.shape[0]
    for i in range(num_nodes):
        neighbors = set(np.nonzero(m[i])[0])
        gr[i] = neighbors
    return gr


def colorGraph(matrix, scc):
    G = nx.DiGraph(matrix)
    pos = nx.spring_layout(G)
    colors = ['red', 'green', 'blue', 'yellow', 'orange', 'violet', 'pink']
    for component, color in zip(scc, colors):
        nx.draw_networkx_nodes(G, pos, nodelist=component, node_color=color, node_size=500)
    nx.draw_networkx_edges(G, pos, arrows=True)
    nx.draw_networkx_labels(G, pos)
    plt.axis('off')
    # plt.savefig('graph.png')
    plt.show()