Coverage for src / competitive_verifier / models / _scc.py: 100%

1"""Strongly Connected Component Graph. 

2 

3Copy from ac-library-python 

4https://github.com/not522/ac-library-python/blob/58f324ec020d57191e7b9e4957b0c5feb5ed3aff/atcoder/_scc.py 

5""" 

6 

7import sys 

8 

9 

10class CSR: 

11 def __init__(self, n: int, edges: list[tuple[int, int]]) -> None: 

12 self.start = [0] * (n + 1) 

13 self.elist = [0] * len(edges) 

14 

15 for e in edges: 

16 self.start[e[0] + 1] += 1 

17 

18 for i in range(1, n + 1): 

19 self.start[i] += self.start[i - 1] 

20 

21 counter = self.start.copy() 

22 for e in edges: 

23 self.elist[counter[e[0]]] = e[1] 

24 counter[e[0]] += 1 

25 

26 

27class SccGraph: 

28 """Strongly Connected Component Graph. 

29 

30 Reference: 

31 R. Tarjan, 

32 Depth-First Search and Linear Graph Algorithms 

33 """ 

34 

35 def __init__(self, n: int) -> None: 

36 self._n = n 

37 self._edges: list[tuple[int, int]] = [] 

38 

39 def add_edge(self, from_vertex: int, to_vertex: int) -> None: 

40 self._edges.append((from_vertex, to_vertex)) 

41 

42 def scc_ids(self) -> tuple[int, list[int]]: 

43 g = CSR(self._n, self._edges) 

44 now_ord = 0 

45 group_num = 0 

46 visited: list[int] = [] 

47 low = [0] * self._n 

48 order = [-1] * self._n 

49 ids = [0] * self._n 

50 

51 sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit())) 

52 

53 def dfs(v: int) -> None: 

54 nonlocal now_ord 

55 nonlocal group_num 

56 nonlocal visited 

57 nonlocal low 

58 nonlocal order 

59 nonlocal ids 

60 

61 low[v] = now_ord 

62 order[v] = now_ord 

63 now_ord += 1 

64 visited.append(v) 

65 for i in range(g.start[v], g.start[v + 1]): 

66 to = g.elist[i] 

67 if order[to] == -1: 

68 dfs(to) 

69 low[v] = min(low[v], low[to]) 

70 else: 

71 low[v] = min(low[v], order[to]) 

72 

73 if low[v] == order[v]: 

74 while True: 

75 u = visited[-1] 

76 visited.pop() 

77 order[u] = self._n 

78 ids[u] = group_num 

79 if u == v: 

80 break 

81 group_num += 1 

82 

83 for i in range(self._n): 

84 if order[i] == -1: 

85 dfs(i) 

86 

87 for i in range(self._n): 

88 ids[i] = group_num - 1 - ids[i] 

89 

90 return group_num, ids 

91 

92 def scc(self) -> list[list[int]]: 

93 ids = self.scc_ids() 

94 group_num = ids[0] 

95 counts = [0] * group_num 

96 for x in ids[1]: 

97 counts[x] += 1 

98 groups: list[list[int]] = [[] for _ in range(group_num)] 

99 for i in range(self._n): 

100 groups[ids[1][i]].append(i) 

101 

102 return groups