summaryrefslogtreecommitdiff
path: root/sources/acyclicity.py
blob: 40cdd2872ca1f3f56bee8f8d7e8e037edda5ecab (plain)
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
# Uses python3

import sys


def explore(adj, v, visited, prev, postv, clock):
    visited.append(v)
    prev[v] = clock[0]
    clock[0] = clock[0] + 1

    for n in adj[v]:
        if n not in visited:
            explore(adj, n, visited, prev, postv, clock)

    postv[v] = clock[0]
    clock[0] = clock[0] + 1


def dfs(adj, visited, prev, postv, clock):
    for v in range(len(adj)):
        if v not in visited:
            explore(adj, v, visited, prev, postv, clock)


def acyclic(adj):
    visited = []
    prev = [0 for i in range(len(adj))]
    postv = [0 for i in range(len(adj))]
    clock = [0]
    dfs(adj, visited, prev, postv, clock)

    for u in range(len(adj)):
        for v in adj[u]:
            if postv[u] <= postv[v]:
                return 1
    return 0


if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
    print(acyclic(adj))