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|
s0 t0
s1 t1
:
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.

si and ti 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

 si &ne; ti

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



Sample input:
3 3
0 1
0 2
1 2


Sample output:
0

Submission status: Accepted

Solution code:
#Detectando Ciclos en un grafo
#Se puede mejorar a un mas
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

#dfs...orderに帰りがけ順の逆順を保存
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():
  #input
  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)
  
  #output
  for i in range(v_num):
    if parent[i] != i:
      print(1)
      break
  else:
    print(0)
main()

Submission status: Accepted

Solution code:
from collections import deque
# sts -> start topological sort   
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)
    # Now start deleting elements
    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 -> no of indirected edges to a vertex
incnt=[0]*v
# q -> queue containing nodes with 0 indirected edges
q=deque()
# ans -> topological sorted array
ans=[]
for i in range(e):
    x,y=map(int,input().split())
    g[x].append(y)
sts()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	cycle_detection
# CreatedDate:  2020-07-28 21:10:00 +0900
# LastModified: 2020-07-28 21:57:12 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


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()

Submission status: Accepted

Solution code:
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  # depths[i] := the length of the longest path to V_i
    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():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

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)) # multi line with multi param
#st = [[0,1],[0,2],[1,2],[2,3]]
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)
    #print(s,act,visited,G)
    if not s in G:
        act.remove(s)
        return
    for e in G[s]:
        #print(s,e,act)
        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)#has cycle
else:
    print(0)

Submission status: Accepted

Solution code:

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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# トポロジカルソート
def main():
    Graph = [] ##appendのために宣言が必要
    V,E = map(int,input().split())
    # V：頂点数
    # E：辺数
    # 入力受付
    i = 0
    while i < E:
        try:
            Graph.append(list(map(int,input().split())))
            i = i + 1
        except:
            break;
            #または、quit(),os.exit()をして止める。

    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):
                # 入り辺がない頂点が始点になっている行を削除
                # i : 入り辺がない点の番号
                if graph[m][0] == i:
                    graph.pop(m)
                    # popすると行列のサイズが一つ減るので
                    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)

#閉路を持つ場合1,持たない場合0
print(solve(v,e,g))

Submission status: Accepted

Solution code:
from collections import deque

class Graph(): #directed
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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


###############################################################################
# AUXILIARY FUNCTIONS

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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


V,E = map(int,input().split())
can_visit = [[None] * V for _ in range(V)]

for i in range(V):
    for k in range(V):
        can_visit[i][k] = (i == k)

for _ in range(E):
    FROM,TO = map(int,input().split())
    can_visit[FROM][TO] = True

#ワーシャルフロイド
for mid in range(V):
    for start in range(V):
        if can_visit[start][mid] == False:
            continue
        for goal in range(V):
            if can_visit[mid][goal] == False:
                continue
            can_visit[start][goal] = True


for FROM in range(V-1):
    for TO in range(FROM+1,V):
        if can_visit[FROM][TO] == True and can_visit[TO][FROM] == True:
            print("1")
            sys.exit()

print("0")

Submission status: Accepted

Solution code:
#全点最短距離の使い回し

import sys

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

Edge = [[] for _ in range(v)]

for i in range(e):
    inpt = list(map(int, input().split( )))
    Edge[inpt[0]].append(inpt[1])

inf = 10**12


dp = [[inf for _ in range(v)] for __ in range(v)]
for i in range(v):
    for ed in Edge[i]:
        dp[i][ed] = -1
for i in range(v):
    dp[i][i] = 0
"""
・for k,for i, for jの順。for i,j,kだと別物
・dpはkによらず使い回しでよい
"""
for k in range(v):
    for j in range(v):
        for i in range(v):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

for i in range(v):
    if dp[i][i]<0:
        print(1)
        sys.exit()

print(0)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


def dfs(root: int, add_duplicated=True) -> bool:
    global edges, visited, duplicated

    def body(i: int) -> bool:
        visited[i] = True
        for edge in edges[i]:
            if visited[edge]:
                if edge == root:
                    return True
                if add_duplicated:
                    duplicated.add(edge)
                continue
            if body(edge):
                return True
        return False

    return body(root)


if __name__ == "__main__":
    n, m = map(int, input().split())
    edges = [set() for _ in range(n)]  # type: ignore

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

    visited = [False] * n
    duplicated = set()  # type: ignore

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

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

def Topo_sort(x,y):
	co = cl.Counter(n for m in x.values() for n in m)
	S = cl.deque([i for i in range(y) if co[i] == 0])
	while S:
		n = S.popleft()
		yield n
		for i in x[n]:
			co[i] -= 1
			if co[i] <= 0:
				S.append(i)
	if sum(co.values()) != 0:
		print(1)
		exit()
	else:
		print(0)
		exit()
# g = cl.dafaultdict(set)に有向グラフを作成し(g[~] != ~) リストが帰ってくる

v,e = m()

g = cl.defaultdict(set)

for i in range(e):
	s,t = m()
	g[s] |= {t}
a = list(Topo_sort(g,v))

Submission status: Accepted

Solution code:
l,r= [int (i) for i in input().split()]
g = [[] for i in range (l)]

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

def visitd_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
        visitd_from(next_index, origin)

for i in range (l):
    visited =[False for i in range(l)]
    visitd_from(i,i)
    if f==1:
        break
print(f)

Submission status: Accepted

Solution code:
def tansaku(graph,v,v_num,visited,stack):
    visited[v] = True
    stack[v] = True
    for i in range(0,v_num):
        if(graph[v][i] == 1):
            if(visited[i]==False):
                if(tansaku(graph,i,v_num,visited,stack)==True):
                    return True
            elif(stack[i]==True):
                return True
    stack[v] = False
    return False

if __name__ == '__main__':
    v_num,e_num = map(int, input().split())
    graph = [ [0] * v_num for i in range(v_num)]
    for i in range(e_num):
        s,t = map(int, input().split())
        graph[s][t] = 1
    
    closed_cycle_is_found=False
    visited = [False]*v_num
    stack = [False]*v_num
    for i in range(v_num):
        for j in range(v_num):
            if(graph[i][j]==1 and visited[j]==False):
                if(tansaku(graph,j,v_num,visited,stack) == True):
                    closed_cycle_is_found=True
                    break

    if(closed_cycle_is_found):
        print("1")
    else:
        print("0")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

class Stack: 
  
    def __init__(self): 
        self.items = [] 

    def isEmpty(self): 
        return len(self.items)==0  

    def push(self, item): 
        self.items.append(item) 

    def pop(self): 
        return self.items.pop()  

    def peek(self): 
        if not self.isEmpty(): 
            return self.items[len(self.items)-1] 

    def size(self): 
        return len(self.items) 



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

L = []

for e in range(E):
  L.append(list(map(int, input().split())))
  
innode = []
stack = Stack()

for v in range(V):
  indegree = 0
  for l in L:
    if l[1] == v:
      indegree += 1
  innode.append(indegree)
  if indegree == 0:
    stack.push(v)
count = 0  
while not stack.isEmpty():
  node = stack.pop()
  count += 1
  for i in L:
    if i[0] == node:
      innode[i[1]] -= 1
      if innode[i[1]] == 0:
        stack.push(i[1])
  if count == V:
    print(0)
    break
else:
  print(1)

Submission status: Accepted

Solution code:


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


def dfs(s):
    if visit[s] != 1:
        visit[s] = 1
        stack[s] = 1
        for t in p[s]:
            if stack[t] == 1:
                print("1")
                exit()
            else:
                dfs(t)
    stack[s] = 0


visit = [0] * v
stack = [0] * v
for i in range(v):
    dfs(i)
print("0")

Submission status: Accepted

Solution code:
def visit(j, visited, stack, Graph):
    stack[j] = 1
    vflag[j] = 1
    
    for k in Graph[j]:
        if stack[k]:
            return True
        if vflag[k]:
            continue
        if visit(k, vflag, stack, Graph):
            return True
    stack[j] = 0
    return False
 

if __name__=='__main__':
    V,E  = (int(x) for x in  input().split())
    Graph = [[] for i in range(V)]

    for i in range(E):
        s, t = (int(x)for x in input().split())
        Graph[s].append(t)
        
    vflag = [0 for i in range(V)]
    stack = [0 for i in range(V)]
    jdg = 0
    
    for j in range(V):
        if not vflag[j]:
            if visit(j, vflag, stack, Graph):
                jdg = 1
                break
    print(jdg)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def input(f):
    V, E = map(int, f.readline().split())
    s = [None for _ in range(E)]
    t = [None for _ in range(E)]
    for i in range(E):
        s[i], t[i] = map(int, f.readline().split())
    return V, E, s, t

import sys

def solve(V, E, s, t):
    inf = sys.maxint
    dist = [[inf for _ in range(V)] for _ in range(V)]
    
    for i in range(E):
        dist[s[i]][t[i]] = 1
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if i != k and k != j and dist[i][k] != inf and dist[k][j] != inf:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    def has_cycle():
        for i in range(V):
            if dist[i][i] != inf:
                return 1
        return 0
    
    print(has_cycle())


with open('/dev/stdin') as f:
    solve(*input(f))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e7))

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

edges = {}

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

stack = []
visited = set()


def dfs(s: int):
    if s in stack:
        return True
    if s in visited:
        return False
    if s not in edges:
        return False

    stack.append(s)
    visited.add(s)

    for t in edges[s]:
        if dfs(t):
            return True

    stack.pop()
    return False


has_cycle = False

for i in range(n):
    if i in visited:
        continue
    if dfs(i):
        has_cycle = True

print(1 if has_cycle else 0)

Submission status: Accepted

Solution code:
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(200000)


def dfs(i):
    global edges, visited, root, duplicated
    visited[i] = True
    for edge in edges[i]:
        if visited[edge]:
            if edge == root:
                return True
            duplicated.add(edge)
            continue
        if dfs(edge):
            return True


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
root = 0
duplicated = set()

for i in range(n):
    if not visited[i]:
        root = i
        if dfs(i):
            print(1)
            break
else:
    for i in duplicated:
        root = i
        if dfs(i):
            print(1)
            break
    else:
        print(0)

Submission status: Runtime Error

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

for i in range(e):
    s,t = map(int, input().split())
    M[s].append(t)
    if t in L:
        L.remove(t)
  
def dijkstra(s):
    color = [0] * n    
    H =[]
    pq.heappush(H, s)
    while len(H) != 0:
        u1 = pq.heappop(H)
        for v1 in M[u1]:
            if v1 and color[v1] == 1:
                print("1")
                return False
            else:
                color[u1] = 1
                pq.heappush(H, v1)
    return True

if not L:
    print("1")
for i in L:
    flag = False
    if dijkstra(i):
        flag = dijkstra(i)
    else: break

if flag:
    print("0")

Submission status: Runtime Error

Solution code:



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

a = []

for i in range(nv):
    a.append([])

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

done = []

flag = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for s in a[index]:

        if s == 0:
            f = 1
            return
        put_forword(s)

put_forword(0)
print(f)