cp-library

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

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: cp_library/alg/graph/articulation_points_fn.py

Depends on

Verified with

Code

import cp_library.alg.graph.__header__
from typing import Union
from cp_library.alg.graph.dfs_events_fn import DFSEvent, DFSFlags, dfs_events
from math import inf

def articulation_points(G, s: Union[int,list,None] = None):
    '''
    Find articulation points in an undirected graph using DFS events.
    Returns a boolean list that is True for indices where the vertex is an articulation point.
    '''
    N = G.N
    if s is None: s = range(N)
    low, disc, children, ap, time = [inf]*N, [-1]*N, [0]*N, [False]*N, 0    
    flags = DFSFlags.DOWN | DFSFlags.BACK | DFSFlags.UP | DFSFlags.RETURN_PARENTS
    events, parent = dfs_events(G, flags, s)
    for event in events:
        match event:
            case DFSEvent.DOWN, u, v:
                children[u] += 1
                disc[v] = low[v] = time
                time += 1
            case DFSEvent.BACK, u, v:
                if v != parent[u]:
                    low[u] = min(low[u], disc[v])
            case DFSEvent.UP, p, u:
                if parent[p] != -1:
                    low[p] = min(low[p], low[u])
                    ap[p] |= low[u] >= disc[p]
                else:
                    # root case
                    ap[p] |= children[p] > 1    
    return ap
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import Union

from enum import auto, IntFlag, IntEnum

class DFSFlags(IntFlag):
    ENTER = auto()
    DOWN = auto()
    BACK = auto()
    CROSS = auto()
    LEAVE = auto()
    UP = auto()
    MAXDEPTH = auto()

    RETURN_PARENTS = auto()
    RETURN_DEPTHS = auto()
    BACKTRACK = auto()
    CONNECT_ROOTS = auto()

    # Common combinations
    ALL_EDGES = DOWN | BACK | CROSS
    EULER_TOUR = DOWN | UP
    INTERVAL = ENTER | LEAVE
    TOPDOWN = DOWN | CONNECT_ROOTS
    BOTTOMUP = UP | CONNECT_ROOTS
    RETURN_ALL = RETURN_PARENTS | RETURN_DEPTHS

class DFSEvent(IntEnum):
    ENTER = DFSFlags.ENTER 
    DOWN = DFSFlags.DOWN 
    BACK = DFSFlags.BACK 
    CROSS = DFSFlags.CROSS 
    LEAVE = DFSFlags.LEAVE 
    UP = DFSFlags.UP 
    MAXDEPTH = DFSFlags.MAXDEPTH
    

def dfs_events(G, flags: DFSFlags, s: Union[int,list,None] = None, max_depth: Union[int,None] = None):
    if flags == DFSFlags.INTERVAL:
        if max_depth is None:
            return G.dfs_enter_leave(s)
    elif flags == DFSFlags.TOPDOWN:
        edges = G.dfs_topdown(s, DFSFlags.CONNECT_ROOTS in flags)
        return [(DFSEvent.DOWN, p, u) for p,u in edges]
    elif flags == DFSFlags.BOTTOMUP:
        edges = G.dfs_bottomup(s, DFSFlags.CONNECT_ROOTS in flags)
        return [(DFSEvent.UP, p, u) for p,u in edges]
    elif DFSFlags.BACKTRACK in flags:
        return G.dfs_backtrack(s)
    state = [0] * G.N
    child = [0] * G.N
    stack = [0] * G.N
    if DFSFlags.RETURN_PARENTS in flags:
        parents = [-1] * G.N
    if DFSFlags.RETURN_DEPTHS in flags:
        depths = [-1] * G.N

    events = []
    for s in G.starts(s):
        stack[depth := 0] = s
        if DFSFlags.DOWN|DFSFlags.CONNECT_ROOTS in flags:
            events.append((DFSEvent.DOWN,-1,s))
        while depth != -1:
            u = stack[depth]
            
            if not state[u]:
                state[u] = 1
                if DFSFlags.ENTER in flags:
                    events.append((DFSEvent.ENTER, u))
                if DFSFlags.RETURN_DEPTHS in flags:
                    depths[u] = depth
            
            if (c := child[u]) < len(G[u]):
                child[u] += 1
                if (s := state[v := G[u][c]]) == 0: # Unvisited
                    if max_depth is None or depth <= max_depth:
                        if flags & DFSFlags.DOWN:
                            events.append((DFSEvent.DOWN, u, v))
                        stack[depth := depth+1] = v
                        if flags & DFSFlags.RETURN_PARENTS:
                            parents[v] = u
                elif s == 1:  # In progress
                    if flags & DFSFlags.BACK:
                        events.append((DFSEvent.BACK, u, v))
                elif s == 2: # Completed
                    if flags & DFSFlags.CROSS:
                        events.append((DFSEvent.CROSS, u, v))
            else:
                depth -= 1
                state[u] = 0 if DFSFlags.BACKTRACK in flags else 2
                if DFSFlags.LEAVE in flags:
                    events.append((DFSEvent.LEAVE, u))
                if depth != -1 and DFSFlags.UP in flags:
                    events.append((DFSEvent.UP, stack[depth], u))
        if DFSFlags.UP|DFSFlags.CONNECT_ROOTS in flags:
            events.append((DFSEvent.UP,-1,s))
    ret = tuple((events,)) if DFSFlags.RETURN_ALL & flags else events
    if DFSFlags.RETURN_PARENTS in flags:
        ret += (parents,)
    if DFSFlags.RETURN_DEPTHS in flags:
        ret += (depths,)
    return ret
from math import inf

def articulation_points(G, s: Union[int,list,None] = None):
    '''
    Find articulation points in an undirected graph using DFS events.
    Returns a boolean list that is True for indices where the vertex is an articulation point.
    '''
    N = G.N
    if s is None: s = range(N)
    low, disc, children, ap, time = [inf]*N, [-1]*N, [0]*N, [False]*N, 0    
    flags = DFSFlags.DOWN | DFSFlags.BACK | DFSFlags.UP | DFSFlags.RETURN_PARENTS
    events, parent = dfs_events(G, flags, s)
    for event in events:
        match event:
            case DFSEvent.DOWN, u, v:
                children[u] += 1
                disc[v] = low[v] = time
                time += 1
            case DFSEvent.BACK, u, v:
                if v != parent[u]:
                    low[u] = min(low[u], disc[v])
            case DFSEvent.UP, p, u:
                if parent[p] != -1:
                    low[p] = min(low[p], low[u])
                    ap[p] |= low[u] >= disc[p]
                else:
                    # root case
                    ap[p] |= children[p] > 1    
    return ap
Back to top page