fork download
copy 
  1. #python3
  2.  
  3. import sys
  4. from collections import deque
  5.  
  6.  
  7. def createGroups(v,visited,adj,counter,groups):
  8.     if counter not in visited:
  9.         visited[counter] = {}
  10.     print(visited[counter])
  11.     if v not in visited[counter]:
  12.         visited[counter][v] = counter
  13.         if len(groups)==counter:
  14.             groups.append([])
  15.         groups[counter].append(v)
  16.         for a in adj[v]:
  17.             if a not in visited[counter]:
  18.                 createGroups(a,visited,adj,counter,groups)
  19.         counter += 1
  20.     else:
  21.         for a in adj[v]:
  22.             if a not in visited[counter]:
  23.                 createGroups(a,visited,adj,counter,groups)
  24.  
  25.     return counter 
  26.  
  27.  
  28. #searches for all reachable vertices from v, following an adjacency list
  29. def explore(v,visited,adj,counter,groupStart):
  30.     if v not in visited:
  31.         visited[v] = counter
  32.         for a in adj[v]:
  33.             if a not in visited:
  34.                 explore(a,visited,adj,counter,groupStart)
  35.         groupStart[counter] = v
  36.         counter += 1
  37.     else:
  38.         for a in adj[v]:
  39.             if a not in visited:
  40.                 explore(a,visited,adj,counter,groupStart)
  41.     return counter  
  42.  
  43. def relax(u,v,w,dist,prev):
  44.     if dist[u]+w < dist[v]:
  45.         dist[v] = dist[u]+w
  46.         prev[v] = u
  47.  
  48. def bellmanFord(V,E,s):
  49.     dist = [float('inf')] * V
  50.     prev = [None] * V
  51.     dist[s] = 0
  52.  
  53.     for i in range(V-1):
  54.         for edge in E:
  55.             relax(edge[0],edge[1],edge[2],dist,prev)
  56.  
  57.     for e in E:
  58.         u = e[0]
  59.         v = e[1]
  60.         w = e[2]
  61.         if dist[u]+w < dist[v]:
  62.             return 1    
  63.  
  64.     return 0
  65.  
  66.  
  67.  
  68. def negative_cycles(adj,E):
  69.     visited = {}
  70.     counter = 0
  71.     groupStart = {}
  72.     groups = []
  73.  
  74.     for v in range(len(adj)):
  75.         counter = explore(v,visited,adj,counter,groupStart)    
  76.  
  77.     if counter==1:
  78.         return bellmanFord(len(adj), E, 0)
  79.     else:
  80.         c = 0
  81.         while c<counter:
  82.             if bellmanFord(len(adj), E, groupStart[c])==1:
  83.                 return 1
  84.             c +=1
  85.     return 0
  86.  
  87.  
  88. if __name__ == '__main__':
  89.     input = sys.stdin.read()
  90.     data = list(map(int, input.split()))
  91.     n, m = data[0:2]
  92.     data = data[2:]
  93.     edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3]))
  94.     data = data[3 * m:]
  95.     adj = [[] for _ in range(n)]
  96.     cost = [[] for _ in range(n)]
  97.     for ((a, b), w) in edges:
  98.         adj[a - 1].append(b - 1)
  99.         cost[a - 1].append(w)
  100.  
  101.     edg = []
  102.     for e in edges:
  103.         edg.append([e[0][0]-1,e[0][1]-1,e[1]])
  104.  
  105.     print(negative_cycles(adj, edg))
  106.  
  107.  
Success #stdin #stdout 0.01s 10376KB
comments (?)
stdin
copy 
4 4
1 2 -5
4 1 2
2 3 2
3 1 1
stdout
copy 
1
https://ideone.com/cczJjq
language:
Python 3 (python  3.12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!