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: Wrong Answer

Solution code:
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): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        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(0 if topological_sort(V, E) is None else 1)

Submission status: Wrong Answer

Solution code:
def is_contain_cycle(g, v):
    route = [None]
    dfs_stack = [(0, None)]            
    while dfs_stack:
        u, prev = dfs_stack.pop()
        if u in route:
            return True
        dfs_stack.extend((v, u) for v in g[u])
        while route[-1] != prev:
            route.pop()
        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)

Submission status: Wrong Answer

Solution code:
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()
            visited |= {u}
            if u in route:
                return True
            dfs_stack.extend((v, u) for v in g[u])
            while route[-1] != prev:
                route.pop()
            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)

Submission status: Wrong Answer

Solution code:
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:
    visited = [False] * n
    for i in duplicated:
        root = i
        if do_dfs(i, False):
            print(1)
            break
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
def dfs(s, visited):
    if s in visited:
        print(1)
        exit()
    else:
        visited.append(s)
        for t in adj[s]:
            dfs(t, visited)
    visited.remove(s)

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

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

dfs(0, [])
print(0)

Submission status: Wrong Answer

Solution code:
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 dijkstra(s):
    color = [0] * n    
    H =[]
    pq.heappush(H, s)
    while len(H) != 0:
        u1 = pq.heappop(H)
        color[u1] = 1
        for v1 in M[u1]:
            if v1 and color[v1] == 1:
                print("1")
                return False
            else:
                pq.heappush(H, v1)
    return True

if dijkstra(0):
    print("0")

Submission status: Wrong Answer

Solution code:
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 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 dijkstra(0):
    print("0")

Submission status: Wrong Answer

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

for i in L:
    flag = False
    if dijkstra(i):
        flag = dijkstra(i)
    else: break

Submission status: Wrong Answer

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")
else:
    for i in L:
        flag = False
        if dijkstra(i):
            flag = dijkstra(i)
        else: break
    if flag:
        print("0")

Submission status: Wrong Answer

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)

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

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

Submission status: Wrong Answer

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 = defaultdict(bool)
def visit(v,p):
    if visited[v]: return
    visited[v] = True
    for k in G[v]:
        if k == p: return True
        return visit(k,p)
    return False

ans = 0
for v in range(V):
    if visit(v, v): ans = 1
print(ans)

Submission status: Wrong Answer

Solution code:

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)

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

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

Submission status: Wrong Answer

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]] == 1):
                result+=1
            if(v_l[e_l[i]] == 0):
                DFS(e_l[i])
    v_l[u] = 2

DFS(0)
print(result)

Submission status: Wrong Answer

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

DFS(0)
print(result)

Submission status: Wrong Answer

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(0)
print(result)

Submission status: Wrong Answer

Solution code:

v, e = map(int, input().split()) # 頂点数vと辺数eを入力

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)] # 全て未探索
ans = 0

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


print(dfs(0))

Submission status: Wrong Answer

Solution code:

v, e = map(int, input().split()) # 頂点数vと辺数eを入力

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


print(dfs(0))

Submission status: Wrong Answer

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 = []

def put_forword(index):

    if index in done:
        return 0

    done.append(index)

    for s in a[index]:
        
        if s == 0:
            return 1

        return put_forword(s)
    return 0


print(put_forword(0))

Submission status: Wrong Answer

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 = []

f = 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)

Submission status: Wrong Answer

Solution code:

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)

done = []
f = 0

def put_forword(index):
    global f

    if index in done:
        return

    done.append(index)

    for i in g[index]:

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

put_forword(0)

print(f)

Submission status: Wrong Answer

Solution code:

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 = [False for i in range(nv)]
f = 0

def pursue_from(index):
    global f


    if visited[index]:
        return

    visited[index] = True

    for next_index in g[index]:

        if next_index == 0:
            f = 1
            return
        pursue_from(next_index)

pursue_from(0)

print(f)

Submission status: Wrong Answer

Solution code:

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 = [False for i in range(nv)]
f = 0

def pursue_from(index, origin):
    global f

    if f == 1 or visited[index]:
        return

    visited[index] = True

    for next_index in g[index]:

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

for i in range(nv):
    pursue_from(i, i)

print(f)

Submission status: Wrong Answer

Solution code:

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 = [False for i in range(nv)]
f = 0

def pursue_from(index, origin):
    global f

    if f == 1 or visited[index]:
        return

    visited[index] = True

    for next_index in g[index]:

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

for i in range(nv):
    pursue_from(i, i)

print(f)

Submission status: Wrong Answer

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):
                print(stackV)
                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))
    print(veri)
    if(True in veri):print(1)
    else:print(0)
        
main()

Submission status: Time Limit Exceeded

Solution code:
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()
                
            visited |= {u}
            if u in route:
                return True
            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)

Submission status: Time Limit Exceeded

Solution code:
from collections import UserList
class Stack(UserList):
    def __init__(self, *args):
        UserList.__init__(self, *args)
        self.contains = set()
    def __contains__(self, x):
        return x in self.contains
    def __and__(self, x):
        return self.contains & x
    def push(self, x):
        if x in self.contains:
            return
        self.data.append(x)
        self.contains |= {x}
    def pop(self):
        x = self.data.pop()
        self.contains -= {x}
        return x

def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        route = Stack([None])
        dfs_stack = [(i, None)]            
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
                
            visited |= {u}
            if u in route:
                return True
            dfs_stack.extend((v, u) for v in g[u])
            
            route.push(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)

Submission status: Time Limit Exceeded

Solution code:
def dfs(s, stack):
    visited[s] = 1
    if s in stack:
        print(1)
        exit()
    else:
        stack.append(s)
        for t in adj[s]:
            dfs(t, stack)
        stack.remove(s)

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

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

while sum(visited) < nv:
    r = 0
    while visited[r]: r += 1
    dfs(r, [])

print(0)

Submission status: Time Limit Exceeded

Solution code:

v, e = map(int, input().split()) # 頂点数vと辺数eを入力

g = [[] for i in range(v)] # グラフの要素数を確保

for i in range(e):
 s, t = map(int, input().split()) 
 g[s].append(t) # グラフに辺を挿入


ans = 0 # 答え
color = ['WHITE' for i in range(v)] # 全て未探索
stack = []
color[0] = 'GRAY'
stack.append(0)

while len(stack) != 0:
 u = stack.pop()

 for adj in g[u]:
  if color[adj] == 'GRAY':
   ans = 1
   stack.clear()
   break
  elif color[adj] == 'WHITE':
   stack.append(adj)
   color[adj] == 'GRAY'

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_4_A: Path/Cycle - Cycle Detection for a Directed Graph


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

Submission status: Accepted

Solution code:
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): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        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)

Submission status: Accepted

Solution code:
def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        #route = Stack([None])
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# Cycle Detection for a Directed Graph
[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)

Submission status: Accepted

Solution code:

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

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:

v, e = map(int, input().split()) # 頂点数vと辺数eを入力

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)

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

Solution code:
#Detectando Ciclos en un grafo
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()