Problem:
Cycle Detection for a Directed Graph Find a cycle in a directed graph G(V, E) . Input A directed graph G is given in the following format:  |V|  |E|  s 0  t 0  s 1  t 1 : s |E|-1  t |E|-1   |V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V| -1 respectively.  s i and t i represent source and target nodes of i -th edge (directed). Output Print 1 if G has cycle(s), 0 otherwise. Constraints  1 ≤ |V| ≤ 100  0 ≤ |E| ≤ 1,000   s i ≠ t i  Sample Input 1 3 3
0 1
0 2
1 2 Sample Output 1 0 Sample Input 2 3 3
0 1
1 2
2 0 Sample Output 2 1

Solution (Python):




from collections import namedtuple

DirectedEdge = namedtuple('DirectedEdge', ('src', 'dest'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def has_cycle(graph):
    def dfs(v):
        if visited[v]:
            if not left[v]:
                return True
        else:
            visited[v] = True
            for e in graph.adj(v):
                if dfs(e.dest):
                    return True
            left[v] = True
        return False

    visited = [False] * graph.v
    left = [False] * graph.v

    for v in range(graph.v):
        if not visited[v] and dfs(v):
            return True

    return False


def run():
    v, e = [int(i) for i in input().split()]
    g = Digraph(v)

    for _ in range(e):
        s, t = [int(i) for i in input().split()]
        g.add(DirectedEdge(s, t))

    if has_cycle(g):
        print("1")
    else:
        print("0")


if __name__ == '__main__':
    run()

Solution (Python):
from collections import deque, defaultdict

def topological_sort(V, E):
    '''
    Kahn's Algorithm (O(|V| + |E|) time)
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the digraph
    E: the adjacency list of the digraph (dict)
    Output:
    If the input digraph is acyclic, then return a topological sorting of the digraph.
    Else, return None.
    '''
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): 
        return top_sorted
    else: 
        return None

N, M = map(int, input().split())
V = range(N)
E = defaultdict(list)
for _ in range(M):
    s, t = map(int, input().split())
    E[s].append(t)
print(1 if topological_sort(V, E) is None else 0)

Solution (Python):
def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        
        route = [None]
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
            if u in route:
                return True
            if u in visited:
                continue
            visited |= {u}
            dfs_stack.extend((v, u) for v in g[u])
            route.append(u)
    return False

from sys import stdin
from collections import defaultdict


readline = stdin.readline

v, e = map(int, readline().split())
g = defaultdict(set)
for i in range(e):
    s, t = map(int, readline().split())
    g[s] |= {t}
print(1 if is_contain_cycle(g, v) else 0)

Solution (Python):
import sys

sys.setrecursionlimit(200000)


def do_dfs(root, add_duplicated=True):
    global edges, visited, duplicated

    def main(i):
        visited[i] = True
        for edge in edges[i]:
            if visited[edge]:
                if edge == root:
                    return True
                if add_duplicated:
                    duplicated.add(edge)
                continue
            if main(edge):
                return True
        return False

    return main(root)


n, m = map(int, input().split())

edges = [set() for _ in range(n)]

for _ in range(m):
    s, t = map(int, input().split())
    edges[s].add(t)

visited = [False] * n
duplicated = set()

for i in range(n):
    if not visited[i]:
        if do_dfs(i):
            print(1)
            break
else:
    for i in duplicated:
        visited = [False] * n
        if do_dfs(i, False):
            print(1)
            break
    else:
        print(0)

Solution (Python):
V, E = map(int, raw_input().split())
cost = [[10**9]*V for i in xrange(V)]
for i in xrange(E):
    s, t = map(int, raw_input().split())
    cost[s][t] = -1
for i in xrange(V):
    cost[i][i] = 0

for k in xrange(V):
    for i in xrange(V):
        for j in xrange(V):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
print any(cost[i][i]<0 for i in xrange(V))/1

Solution (Python):



"""
input:
3 3
0 1
0 2
1 2

output:
0
"""

import sys


def generate_graph_table(edges):
    for edge in edges:
        source, target = map(int, edge)
        init_adj_table[source].append(target)

    return init_adj_table


def graph_dfs(current, visited, stack):
    if not visited[current]:
        visited[current] = True
        stack[current] = True

        for adj in adj_table[current]:
            if not visited[adj] and graph_dfs(adj, visited, stack):
                return True
            elif stack[adj]:
                return True

    stack[current] = False
    return False


def check_cyclic():
    visited, stack = ([False] * v_num for _ in range(2))
    for v in range(v_num):
        if graph_dfs(v, visited, stack):
            return True
    return False


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    c_edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(list() for _ in range(v_num))
    adj_table = generate_graph_table(c_edges)

    print(int(check_cyclic()))

Solution (Python):
def dfs(s):
    if not visited[s]:
        visited[s] = True
        stack[s] = True
        for t in adj[s]:
            if stack[t]:
                print(1)
                exit()
            else:
                dfs(t)
    stack[s] = False

nv, ne = map(int, input().split(' '))
adj = [[] for _ in range(nv)]
visited = [False] * nv
stack = [False] * nv

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s].append(t)

for i in range(nv):
    dfs(i)

print(0)

Solution (Python):
import heapq as pq
inf = float("inf")
n,e = map(int, input().split())
M = [[] for i in range(n)]

for i in range(e):
    s,t = map(int, input().split())
    M[s].append(t)

def dfs(s):
    if not visit[s]:
        visit[s] = True
        stack[s] = True
        for t in M[s]:
            if stack[t]:
                print(1)
                exit()
            else: dfs(t)
    stack[s] = False

visit = [False for _ in range(n)]
stack = [False for _ in range(n)]
for i in range(n):
    dfs(i)
print("0")

Solution (Python):
def main():
    nvertices, nedges = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        s, t = map(int, input().split())
        Adj[s].append(t)

    visited = [0 for i in range(nvertices)]
    stack = [0 for i in range(nvertices)]
    ans = 0
    for u in range(nvertices):
        if not visited[u]:
            if dfs(u, visited, stack, Adj):
                ans = 1
                break
    print(ans)


def dfs(u, visited, stack, Adj):
    stack[u] = visited[u] = 1
    for v in Adj[u]:
        if stack[v]:
            return True
        if visited[v]:
            continue
        if dfs(v, visited, stack, Adj):
            return True
    stack[u] = 0
    return False


main()

Solution (Python):
from collections import defaultdict

V, E = map(int, input().split())
G = defaultdict(list)

for i in range(E):
    s, t = map(int, input().split())
    G[s].append(t)

visited = None
p = None
def dfs(v):
    visited[v] = True
    for k in G[v]:
        if k == p:
            print(1)
            exit()
        if not visited[k]: dfs(k)

for v in range(V):
    p = v
    visited = defaultdict(bool)
    dfs(v)
print(0)

Solution (Python):
from collections import defaultdict
def dfs(here, track, went, connect):
    for c in connect[here]:
        if track[c]:
            return True
        elif c not in went:
            went |= {c}
            track[c] = 1
            if dfs(c, track, went, connect):
                return True
    track[here] = 0
    return False

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
went = set()
track = [0 for n in range(vertices)]
for v in range(vertices):
    if v not in went and dfs(v, track, went, connect):
        print(1)
        break
else:
    print(0)

Solution (Python):

[vertex, edge] = list(map(int, input("").split()))
array = [[0 for j in range(vertex)] for i in range(vertex)]

for i in range(edge):
    data = list(map(int, input("").split()))
    array[data[0]][data[1]] = 1

visited = [0 for j in range(vertex)]
result = 0

def dfs(node, goal):
    for t in range(vertex):
        visited[node] = 1
        if array[node][t] != 0 and t == goal:
            global result
            result = 1
        if array[node][t] != 0 and visited[t] == 0:
            dfs(t, goal)

for i in range(vertex):
    visited = [0 for j in range(vertex)]
    dfs(i,i)
    if result == 1:
        print(1)
        break

if result == 0:
    print(0)

Solution (Python):

[vertex, edge] = list(map(int, input("").split()))
array = [[0 for j in range(vertex)] for i in range(vertex)]

for i in range(edge):
    data = list(map(int, input("").split()))
    array[data[0]][data[1]] = 1

visited = [0 for j in range(vertex)]
result = 0

def dfs(node, goal):
    for t in range(vertex):
        visited[node] = 1
        if array[node][t] != 0 and t == goal:
            global result
            result = 1
        if array[node][t] != 0 and visited[t] == 0:
            dfs(t, goal)

for i in range(vertex):
    visited = [0 for j in range(vertex)]
    dfs(i,i)
    if result == 1:
        print(1)
        break

if result == 0:
    print(0)

Solution (Python):

[vertex, edge] = list(map(int, input("").split()))
array = [[0 for j in range(vertex)] for i in range(vertex)]

for i in range(edge):
    data = list(map(int, input("").split()))
    array[data[0]][data[1]] = 1

visited = [0 for j in range(vertex)]
result = 0

def dfs(node, goal):
    for t in range(vertex):
        visited[node] = 1
        if array[node][t] != 0 and t == goal:
            global result
            result = 1
        if array[node][t] != 0 and visited[t] == 0:
            dfs(t, goal)

for i in range(vertex):
    visited = [0 for j in range(vertex)]
    dfs(i,i)
    if result == 1:
        print(1)
        break

if result == 0:
    print(0)

Solution (Python):

[vertex, edge] = list(map(int, input("").split()))
array = [[0 for j in range(vertex)] for i in range(vertex)]

for i in range(edge):
    data = list(map(int, input("").split()))
    array[data[0]][data[1]] = 1

visited = [0 for j in range(vertex)]
result = 0

def dfs(node, goal):
    for t in range(vertex):
        visited[node] = 1
        if array[node][t] != 0 and t == goal:
            global result
            result = 1
        if array[node][t] != 0 and visited[t] == 0:
            dfs(t, goal)

for i in range(vertex):
    visited = [0 for j in range(vertex)]
    dfs(i,i)
    if result == 1:
        print(1)
        break

if result == 0:
    print(0)

Solution (Python):

n_V, n_E = map(int, input().split())

G = [[] for i in range(n_V)]


for i in range(n_E):
    v, e = map(int, input().split())
    G[v].append(e)


flag = False

for i in range(n_V):
    stack = [i]
    visited = set()

    while stack != []:
        current = stack.pop()

        for e in G[current]:
            if e == i:
                flag = True
                break

            if e not in stack and e not in visited:
                stack.append(e)

        visited.add(current)


print(int(flag))

Solution (Python):
import sys;

v,e=map(int, input().split());

v_l=[0]*v;
e_b=[0]*e;
e_l=[0]*e;
result=0;

for i in range(v):
    v_l[i] = 0;
for i in range(e):
    e_b[i], e_l[i] = map(int, input().split());

def DFS(u):
    global result
    global v_l
    v_l[u] = 1
    for i in range(e):
        if(e_b[i] == u):
            if(v_l[e_l[i]] == 0):
                DFS(e_l[i])
            if(v_l[e_l[i]] == 1):
                result=1
    v_l[u] = 2
for i in range(v):
    DFS(i)
print(result)

Solution (Python):

v, e = map(int, input().split()) 

g = [[] for i in range(v)] 

for i in range(e):
 s, t = map(int, input().split()) 
 g[s].append(t) 


color = ['WHITE' for i in range(v)] 

def dfs(u):
 color[u] = 'GRAY'

 for adj in g[u]:
  if color[adj] == 'GRAY':
   return 1
  elif color[adj] == 'WHITE':
   if dfs(adj) == 1:
    return 1

 color[u] = 'BLACK'
 return 0

ans = 0
for u in range(v):
 color[i in range(v)] = 'WHITE'
 if dfs(u) == 1:
  ans = 1
  break

print(ans)

Solution (Python):

nv,ne = [int(i) for i in input().split()]

g = [[] for i in range(nv)]

for i in range(ne):
    s,t = [int(j) for j in input().split()]
    g[s].append(t)

visited = []
f = 0

def pursue_from(index, origin):

    if visited[index]:
        return

    visited[index] = True

    for next_index in g[index]:

        if next_index == origin:
            global f
            f = 1
            return
        pursue_from(next_index, origin)

for i in range(nv):
    visited = [False for i in range(nv)]

    pursue_from(i, i)

    if f == 1:
         break

print(f)

Solution (Python):

from collections import deque
import sys

def dfs(G,u):
    n = len(G)
    vis=[-1]*n
    stackV = []
    pila = deque()
    pila.append(u)
    vis[u]=1
    stackV.append(u)
    while(pila):
        w = pila.pop()
        for v in G[w]:
            if(vis[v]==-1):
                vis[v]=1
                pila.append(v)
                stackV.append(v)
            elif(vis[v]==1 and v==u):
                return True
    return False

def main():
    G =[]
    val = [int(x) for x in sys.stdin.readline().strip().split()]
    for i in range(val[0]):
        G.append([])
    for i in range(val[1]):
        L = [int(x) for x in sys.stdin.readline().strip().split()]
        G[L[0]].append(L[1])
    veri=[]

    for i in range(val[0]):
        veri.append(dfs(G,i))
    
    if(True in veri):print(1)
    else:print(0)
        
main()

Solution (Python):


from collections import deque
import sys

def dfs(G,u):
    n = len(G)
    vis=[-1]*n
    stackV = []
    pila = deque()
    pila.append(u)
    vis[u]=1
    stackV.append(u)
    while(pila):
        w = pila.pop()
        for v in G[w]:
            if(vis[v]==-1):
                vis[v]=1
                pila.append(v)
                stackV.append(v)
            elif(vis[v]==1 and v==u):
                return True
    return False

def main():
    G =[]
    val = [int(x) for x in sys.stdin.readline().strip().split()]
    for i in range(val[0]):
        G.append([])
    for i in range(val[1]):
        L = [int(x) for x in sys.stdin.readline().strip().split()]
        G[L[0]].append(L[1]) 
    veri=[]

    for i in range(val[0]):
        veri.append(dfs(G,i))
    if(True in veri):print(1)
    else:print(0)
        
main()

Solution (Python):
import sys;

v,e=map(int, input().split());

v_l=[0]*v;
e_b=[0]*e;
e_l=[0]*e;
result=0;

for i in range(v):
    v_l[i] = 0;
for i in range(e):
    e_b[i], e_l[i] = map(int, input().split());

def DFS(u):
    global result
    global v_l
    v_l[u] = 1
    for i in range(e):
        if(e_b[i] == u):
            if(v_l[e_l[i]] == 0):
                DFS(e_l[i])
            if(v_l[e_l[i]] == 1):
                result=1
    v_l[u] = 2

for i in range(v):
    DFS(i)
print(result)

Solution (Python):
import sys;

v,e=map(int, input().split());

v_l=[0]*v;
e_b=[0]*e;
e_l=[0]*e;
result=0;

for i in range(v):
    v_l[i] = 0;
for i in range(e):
    e_b[i], e_l[i] = map(int, input().split());

def DFS(u):
    global result
    global v_l
    v_l[u] = 1
    for i in range(e):
        if(e_b[i] == u):
            if(v_l[e_l[i]] == 0):
                DFS(e_l[i])
            if(v_l[e_l[i]] == 1):
                result=1
    v_l[u] = 2

for i in range(v):
    DFS(i)
print(result)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def dfs(v, visited, edges, order):
  visited[v] = True
  for to in edges[v]:
    if not visited[to]:
      dfs(to, visited, edges, order)
  order.append(v)


def search_strongly_connection(v, visited, reverse_edges, parent, num):
  visited[v] = True
  for to in reverse_edges[v]:
    if not visited[to]:
      parent[to] = num
      search_strongly_connection(to, visited, reverse_edges, parent, num)

def main():
  
  v_num , e_num = map(int, input().split())
  edges = [[] for _ in range(v_num)]
  reverse_edges = [[] for _ in range(v_num)]
  for _ in range(e_num):
    s, t = map(int, input().split())
    edges[s].append(t)
    reverse_edges[t].append(s)
  
  
  order = []
  visited = [False] * v_num
  for v in range(v_num):
    if not visited[v]:
      dfs(v, visited, edges, order)
  order.reverse()
  
  
  visited = [False] * v_num
  parent = [i for i in range(v_num)]
  for v in order:
    if not visited[v]:
      search_strongly_connection(v, visited, reverse_edges, parent, v)
  
  
  for i in range(v_num):
    if parent[i] != i:
      print(1)
      break
  else:
    print(0)
main()

Solution (Python):
from collections import deque

def sts():
    for i in g:
        for j in i:
            incnt[j]+=1 
    for i in range(v):
        if incnt[i]==0:
            q.append(i)
    
    while q:
        e=q.popleft()
        ans.append(e)
        for i in g[e]:
            incnt[i]-=1
            if incnt[i]==0:
                q.append(i)
    if len(ans)==v: print(0)
    else: print(1)

            
v,e=map(int,input().split())
g=[[] for i in range(v)]

incnt=[0]*v

q=deque()

ans=[]
for i in range(e):
    x,y=map(int,input().split())
    g[x].append(y)
sts()

Solution (Python):
def main():
    n, m = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a].append(b) for a, b in abc]

    def closed2(start, g_set, visited):
        root = [start]
        root_set = {start}
        r = 1
        while root_set:
            now = root[r-1]
            if r == 1:
                past = -1
            else:
                past = root[r-2]
            if len(g_set[now]) > 0:
                j = g_set[now].pop()
                if j == past:
                    continue
                if j in root_set:
                    return root
                now = j
                root.append(j)
                root_set.add(j)
                visited.add(j)
                r += 1
            else:
                root_set.remove(now)
                now = past
                root.pop()
                r -= 1
        return []

    def closed(g):
        g_set = [set(i) for i in g]
        visited = set()
        for i in range(n):
            if i in visited:
                continue
            visited.add(i)
            ret = closed2(i, g_set, visited)
            if ret != []:
                return ret
        return []

    print(int(len(closed(g)) > 0))


main()

Solution (Python):









import os
import sys




class Graph():
    def __init__(self, vertex):
        self.V = vertex
        self.path = [[] for _ in range(self.V)]
        self.visited = [False] * self.V
        self.recurbox = [False] * self.V

    def addedge(self, s, t):
        self.path[s].append(t)

    def dfs(self, u):
        self.visited[u] = True
        self.recurbox[u] = True
        for v in self.path[u]:
            if self.visited[v] is False:
                if self.dfs(v) is True:
                    return True
            elif self.recurbox[v] is True:
                return True
        self.recurbox[u] = False
        return False

    def dfsutil(self):
        for i in range(self.V):
            if self.visited[i] is False:
                if self.dfs(i) is True:
                    return True
        return False


def main():
    V, E = map(int, input().split())
    graph = Graph(V)
    for _ in range(E):
        s, t = map(int, input().split())
        graph.addedge(s, t)
    if graph.dfsutil() is True:
        print(1)
    else:
        print(0)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def grl_4_a():
    
    V, _, *ST = map(int, open(0).read().split())
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print(1 if res is None else 0)


if __name__ == "__main__":
    grl_4_a()

Solution (Python):









import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

V,E = map(int,sys.stdin.readline().split())
st = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) 

G = {i:[] for i in range(V)}

for s,t in st:
    G[s].append(t)

def dfs_cycle(s):
    act.add(s)
    visited.add(s)
    
    if not s in G:
        act.remove(s)
        return
    for e in G[s]:
        
        if e in act:
            global bad
            bad = True
            return
        elif not e in visited:
            dfs_cycle(e)
    act.remove(s)

bad = False
visited = set()
act = set()
for s,_ in st:
    if not s in visited:
        dfs_cycle(s)
if bad:
    print(1)
else:
    print(0)

Solution (Python):

def main():
    v,e = map(int,input().split())
    E = [[] for _ in range(v)]
    for _ in range(e):
        s,t = map(int,input().split())
        E[s].append(t)

    res = False
    visited = [False]*v
    checked = [False]*v
    def dfs(u):
        if visited[u]:
            nonlocal res
            res = True
            return
        visited[u] = True
        for nu in E[u]:
            if not checked[nu]:dfs(nu)
        visited[u] = False
        checked[u] = True

    for i in range(v):
        for j in range(v):visited[j] = False
        if not checked[i]:dfs(i)
    print (1 if res else 0)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
from collections import defaultdict

class Graph:
    def __init__(self,vertices):
        self.graph=defaultdict(list)
        self.V=vertices

    def addEdge(self,u,v):
        self.graph[u].append(v)

def isCycle(n,graph):

    in_degree=[0]*n

    for i in range(n):
        for j in graph[i]:
            in_degree[j]+=1

    queue=[]
    for i in range(len(in_degree)):
        if in_degree[i]==0:
            queue.append(i)

    counter=0

    while(queue):

        nu=queue.pop(0)

        for v in graph[nu]:
            in_degree[v]-=1

            if in_degree[v]==0:
                queue.append(v)
        counter+=1
    if counter==n:
        return False
    else:
        return True


if __name__=='__main__':

    V, E, = (int(x) for x in input().split())
    g = Graph(V)
    for i in range(E):
        v, e = (int(x) for x in input().split())
        g.addEdge(v,e)

    if(True == isCycle(g.V,g.graph)):
        print("1")
    else:
        print("0")

Solution (Python):

def main():
    Graph = [] 
    V,E = map(int,input().split())
    
    
    
    i = 0
    while i < E:
        try:
            Graph.append(list(map(int,input().split())))
            i = i + 1
        except:
            break;
            

    point_dict = {}
    result = topological_sort(V,E,Graph,point_dict)
    print(result)


def initialize(v,pdict):
    i = 0
    while i < v:
        pdict[i] = 0
        i = i + 1
    return pdict


def count_node(graph,pdict):
    i = 0
    while i < len(graph):
        pdict[graph[i][1]] = pdict[graph[i][1]] + 1
        i = i + 1
    return pdict


def remove_point(graph,pdict):
    i = 0
    count_remove = 0
    
    while i < len(pdict):
        if pdict[i] == 0:
            m = 0
            while m < len(graph):
                
                
                if graph[m][0] == i:
                    graph.pop(m)
                    
                    m = m - 1
                    count_remove = count_remove + 1
                m = m + 1
        i = i + 1
    return (graph,count_remove)

def topological_sort(v,e,graph,pdict):
    pdict = initialize(v, pdict)
    pdict = count_node(graph,pdict)
    """
    print()
    print("Graph")
    print(graph)
    print("pdict")
    print(pdict)
    """
    graph,count_remove = remove_point(graph, pdict)
    """
    print("Graph_Remove")
    print(graph)
    print(count_remove)
    print("-----------------------------")
    """
    if len(graph) == 0:
        return 0
    elif count_remove == 0:
        return 1
    elif count_remove > 0:
        return topological_sort(v,e,graph,pdict)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

V, E = map(int, input().split())
G = defaultdict(list)

for i in range(E):
    s, t = map(int, input().split())
    G[s].append(t)

visited = None
p = None
def dfs(v):
    visited[v] = True
    for k in G[v]:
        if k == p:
            print(1)
            exit()
        if not visited[k]: dfs(k)

for v in range(V):
    p = v
    visited = defaultdict(bool)
    dfs(v)
print(0)

Solution (Python):
from collections import deque, defaultdict

v, e = map(int, input().split())
st = [[int(x) for x in input().split()] for  _ in range(e)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in st:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

if len(res)!=v: print('1')
else: print('0')

Solution (Python):
def solve(V, E, G):
    done = [False] * V
    def dfs(i, path):
        path.add(i)
        for j in G[i]:
            if j in path:
                return True
            if not done[j] and dfs(j, path):
                return True
        path.remove(i)
        done[i] = True
        return False
    for i in range(V):
        if not done[i] and dfs(i, set()):
            return 1
    return 0

v,e=map(int,input().split())
g=[set() for _ in range(v)]
for _ in range(e):
    s,t=map(int,input().split())
    g[s].add(t)


print(solve(v,e,g))

Solution (Python):
from collections import deque

class Graph(): 
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.deg[e[1]-1] += 1
    def topological_sort(self):
        res = [i for i in range(self.n) if self.deg[i]==0]
        queue = deque(res)
        used = [False for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                self.deg[adj] -= 1
                if self.deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

import sys
input = sys.stdin.readline

V,E = map(int,input().split())
edge = [tuple(map(lambda x:int(x)+1,input().split())) for _ in range(E)]

g = Graph(V,edge)
A = g.topological_sort()

print(0 if len(A)==V else 1)

Solution (Python):
def dfs(s):
	if not visited[s]:
		visited[s] = True
		active[s] = True
		for t in con[s]:
			if active[t] or dfs(t):
				return True
	active[s] = False

v, e, *L = map(int, open(0).read().split())
con = [[] for _ in range(v)]
visited = [False] * v
active = [False] * v
for s, t in zip(*[iter(L)] * 2):
	con[s - 1].append(t - 1)
for i in range(v):
	if dfs(i):
		print(1)
		exit()
print(0)

Solution (Python):
from collections import deque

v,e = map(int,input().split()) 
ins = [0]*v
outs = [[] for i in range(v)]
ans = []
for i in range(e):
    a,b = map(int,input().split())
    outs[a].append(b)
    ins[b] += 1
Q = deque([])
for i in range(v):
    if ins[i] == 0:
        Q.append(i)
while len(Q) > 0:
    cur = Q.popleft()
    ans.append(cur)
    for e in outs[cur]:
        ins[e] -= 1
        if ins[e] == 0:
            Q.append(e)
if len(ans) == v:
    print(0)
else:
    print(1)

Solution (Python):
import sys
Vnum = 0
Enum = 0
Edge = {}
L = []
V = []

def visit(n):
    if V[n] == 1:
        print(1)
        sys.exit()
    elif V[n] == 0:
        V[n] = 1
        if n in Edge.keys():
            for m in Edge[n]:
                visit(m)
        V[n] = 2
        L.append(n)
        return True

Vnum,Enum = map(int,input().split())
V = [ 0 for v in range(Vnum) ]
for _ in range(Enum):
    s,t = map(int,input().split())
    if s in Edge.keys():
        Edge[s].append(t)
    else:
        Edge[s] = [t]

for n in range(Vnum):
    if V[n] == 0:
        visit(n)
L.reverse()
print(0)

Solution (Python):


import os
import sys


def main():
    V, E = read_ints()
    G = [set() for _ in range(V)]
    for _ in range(E):
        s, t = read_ints()
        G[s].add(t)
    print(solve(V, E, G))


def solve(V, E, G):
    done = [False] * V

    def dfs(i, path):
        path.add(i)
        for j in G[i]:
            if j in path:
                return True
            if not done[j] and dfs(j, path):
                return True
        path.remove(i)
        done[i] = True
        return False

    for i in range(V):
        if not done[i] and dfs(i, set()):
            return 1

    return 0





DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    INF = float('inf')
    V, E = map(int, input().split())
    
    G = [[INF for i in range(V)] for j in range(V)]
    
    for i in range(V): G[i][i] = 0
    
    for i in range(E):
        s, t = map(int, input().split())
        G[s][t] = -1
        
    for k in range(V):
        for i in range(V):
            for j in range(V):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
            
    for i in range(V): 
        if G[i][i]: 
            print(1)
            break
    else: print(0)
 
if __name__ == '__main__':
    main()