fork download
copy 
  1. import re
  2.  
  3. def dfs(g, v, visited, p):
  4.     visited[v] = True
  5.     for w in g[v]:
  6.         if not visited[w]: dfs(g, w, visited, p)
  7.     # p.insert(0, v)
  8.     if not p:
  9.         p.append([v])
  10.     else:
  11.         for w in p[0]:
  12.             if w in g[v]:
  13.                 p.insert(0, [v])
  14.                 return
  15.         p[0].append(v)
  16.  
  17. def topological(g):
  18.     visited = [False for i in range(len(g))]
  19.     p = []
  20.     for v in range(len(g)):
  21.         if not visited[v]: dfs(g, v, visited, p)
  22.     return p
  23.  
  24. def add_edges(g, f, t, vertices):
  25.     if '*' not in f and '*' not in t:
  26.         g[vertices[f]].append(vertices[t])
  27.     elif '*' not in f:
  28.         f = vertices[f]
  29.         t = re.sub('\*', '', t)
  30.         for name in vertices:
  31.             if t in name: g[f].append(vertices[name])
  32.     elif '*' not in t:
  33.         f = re.sub('\*', '', f)
  34.         t = vertices[t]
  35.         for name in vertices:
  36.             if f in name: g[vertices[name]].append(t)
  37.     else:
  38.         ff = re.sub('\*', '', f)
  39.         tt = re.sub('\*', '', t)
  40.         for name in vertices:
  41.             if ff in name: add_edges(g, name, t, vertices)
  42.             if tt in name: add_edges(g, f, name, vertices)
  43.  
  44.  
  45. if __name__ == '__main__':
  46.     warning = "Warning: '%s' does not have any ordering."
  47.     N, M = [int(token) for token in raw_input().split()]
  48.  
  49.     vertices = {}
  50.     vertex_names = []
  51.     for i in range(N):
  52.         vertex_names.append(raw_input())
  53.         vertices[vertex_names[-1]] = i
  54.  
  55.     g = {v:[] for v in vertices.values()}
  56.     for i in range(M):
  57.         f, t = raw_input().split()
  58.         add_edges(g, f, t, vertices)
  59.  
  60.     has_order = [False for i in range(N)]
  61.     for v in g:
  62.         for w in g[v]: has_order[w] = True
  63.         if g[v]: has_order[v] = True
  64.  
  65.     od = 1
  66.     for p in topological(g):
  67.         print str(od)+'. '+', '.join(vertex_names[i] for i in p if has_order[i])
  68.         od += 1
  69.  
  70.     if not all(has_order):
  71.         for i in range(N):
  72.             if not has_order[i]: print warning % (vertex_names[i])
Success #stdin #stdout 0.01s 7900KB
comments (?)
stdin
copy 
8 5
turkey
pecan_pie
salad
crab_cakes
almond_pie
rice
coffee
turkey_stuffing
turkey_stuffing turkey
turkey* *_pie
*pie coffee
salad turkey*
crab_cakes salad
stdout
copy 
1. crab_cakes
2. salad
3. turkey_stuffing
4. turkey
5. almond_pie, pecan_pie
6. coffee
Warning: 'rice' does not have any ordering.
https://ideone.com/QdXvGk
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
secret

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!