/
021.py
80 lines (70 loc) · 2.23 KB
/
021.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
input = sys.stdin.readline
class SCC:
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
self.rev_graph = [[] for _ in range(n)]
self.labels = [-1] * n
self.lb_cnt = 0
def add_edge(self, v, nxt_v):
self.graph[v].append(nxt_v)
self.rev_graph[nxt_v].append(v)
def build(self):
self.post_order = []
self.used = [False] * self.n
for v in range(self.n):
if not self.used[v]:
self._dfs(v)
for v in reversed(self.post_order):
if self.labels[v] == -1:
self._rev_dfs(v)
self.lb_cnt += 1
def _dfs(self, v):
stack = [v, 0]
while stack:
v, idx = stack[-2:]
if not idx and self.used[v]:
stack.pop()
stack.pop()
else:
self.used[v] = True
if idx < len(self.graph[v]):
stack[-1] += 1
stack.append(self.graph[v][idx])
stack.append(0)
else:
stack.pop()
self.post_order.append(stack.pop())
def _rev_dfs(self, v):
stack = [v]
self.labels[v] = self.lb_cnt
while stack:
v = stack.pop()
for nxt_v in self.rev_graph[v]:
if self.labels[nxt_v] != -1:
continue
stack.append(nxt_v)
self.labels[nxt_v] = self.lb_cnt
def construct(self):
self.dag = [[] for i in range(self.lb_cnt)]
self.groups = [[] for i in range(self.lb_cnt)]
for v, lb in enumerate(self.labels):
for nxt_v in self.graph[v]:
nxt_lb = self.labels[nxt_v]
if lb == nxt_lb:
continue
self.dag[lb].append(nxt_lb)
self.groups[lb].append(v)
return self.dag, self.groups
n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(m)]
scc = SCC(n)
for u, v in graph:
scc.add_edge(u - 1, v - 1)
scc.build()
_,elems = scc.construct()
ans = 0
for i in range(len(elems)):
ans += len(elems[i]) * (len(elems[i]) - 1) // 2
print(ans)