cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:warning: cp_library/alg/graph/strongly_connected_components_fn.py

Depends on

Code

import cp_library.alg.graph.__header__
from typing import Iterator
from cp_library.alg.iter.slice_iterator_reverse_cls import SliceIteratorReverse
from cp_library.alg.dp.chmin_fn import chmin
from cp_library.ds.elist_fn import elist
from cp_library.ds.array_init_fn import i32f, u32f, u8f

def strongly_connected_components(G) -> Iterator[list[int]]:
    '''
    Finds strongly connected sccs in directed graph using Tarjan's algorithm.
    Returns sccs in topological order.
    '''
    tin, low, on_stack, time = i32f(N := G.N, -1), u32f(N), u8f(N), 0
    order, sccs, L = elist(N), elist(N), elist(N)
    
    def enter(u):
        nonlocal time
        tin[u] = low[u] = (time := time+1)
        order.append(u)
        on_stack[u] = 1

    def back_or_cross(u,v):
        if on_stack[v]: chmin(low, u, tin[v])

    def leave(u):
        if low[u] == tin[u]:
            L.append(len(sccs))
            while True:
                on_stack[v := order.pop()] = 0
                sccs.append(v)
                if v == u: break

    def up(u,v):
        chmin(low, v, low[u])

    G.dfs(enter_fn=enter, back_fn=back_or_cross, cross_fn=back_or_cross, leave_fn=leave, up_fn=up)
    return SliceIteratorReverse(sccs, L)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import Iterator

from typing import Iterator, SupportsIndex
from typing import TypeVar
_T = TypeVar('T')

class SliceIteratorReverse(Iterator[_T]):
    def __init__(self, A: list[_T], L: list[SupportsIndex]):
        self.A, self.L, self.r = A, L, len(A)
    def __len__(self): return len(self.L)
    def __next__(self):
        L = self.L
        if not L: raise StopIteration
        self.r, r = (l := L.pop()), self.r
        return self.A[l:r]


def chmin(dp, i, v):
    if ch:=dp[i]>v:dp[i]=v
    return ch


def elist(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
    
from typing import Iterable
from array import array

def i8f(N: int, elm: int = 0):      return array('b', (elm,))*N  # signed char
def u8f(N: int, elm: int = 0):      return array('B', (elm,))*N  # unsigned char
def i16f(N: int, elm: int = 0):     return array('h', (elm,))*N  # signed short
def u16f(N: int, elm: int = 0):     return array('H', (elm,))*N  # unsigned short
def i32f(N: int, elm: int = 0):     return array('i', (elm,))*N  # signed int
def u32f(N: int, elm: int = 0):     return array('I', (elm,))*N  # unsigned int
def i64f(N: int, elm: int = 0):     return array('q', (elm,))*N  # signed long long
# def u64f(N: int, elm: int = 0):     return array('Q', (elm,))*N  # unsigned long long
def f32f(N: int, elm: float = 0.0): return array('f', (elm,))*N  # float
def f64f(N: int, elm: float = 0.0): return array('d', (elm,))*N  # double

def i8a(init = None):  return array('b') if init is None else array('b', init)  # signed char
def u8a(init = None):  return array('B') if init is None else array('B', init)  # unsigned char
def i16a(init = None): return array('h') if init is None else array('h', init)  # signed short
def u16a(init = None): return array('H') if init is None else array('H', init)  # unsigned short
def i32a(init = None): return array('i') if init is None else array('i', init)  # signed int
def u32a(init = None): return array('I') if init is None else array('I', init)  # unsigned int
def i64a(init = None): return array('q') if init is None else array('q', init)  # signed long long
# def u64a(init = None): return array('Q') if init is None else array('Q', init)  # unsigned long long
def f32a(init = None): return array('f') if init is None else array('f', init)  # float
def f64a(init = None): return array('d') if init is None else array('d', init)  # double

i8_max = (1 << 7)-1
u8_max = (1 << 8)-1
i16_max = (1 << 15)-1
u16_max = (1 << 16)-1
i32_max = (1 << 31)-1
u32_max = (1 << 32)-1
i64_max = (1 << 63)-1
u64_max = (1 << 64)-1

def strongly_connected_components(G) -> Iterator[list[int]]:
    '''
    Finds strongly connected sccs in directed graph using Tarjan's algorithm.
    Returns sccs in topological order.
    '''
    tin, low, on_stack, time = i32f(N := G.N, -1), u32f(N), u8f(N), 0
    order, sccs, L = elist(N), elist(N), elist(N)
    
    def enter(u):
        nonlocal time
        tin[u] = low[u] = (time := time+1)
        order.append(u)
        on_stack[u] = 1

    def back_or_cross(u,v):
        if on_stack[v]: chmin(low, u, tin[v])

    def leave(u):
        if low[u] == tin[u]:
            L.append(len(sccs))
            while True:
                on_stack[v := order.pop()] = 0
                sccs.append(v)
                if v == u: break

    def up(u,v):
        chmin(low, v, low[u])

    G.dfs(enter_fn=enter, back_fn=back_or_cross, cross_fn=back_or_cross, leave_fn=leave, up_fn=up)
    return SliceIteratorReverse(sccs, L)
Back to top page