Advertisement
Guest User

Untitled

a guest
Dec 12th, 2016
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2.  
  3. def dfs(v):
  4.     used[v] = True
  5.     for i in range(0, len(g[v]), 1):
  6.         if not used[g[v][i]]:
  7.             dfs1(g[v][i])
  8.     order.push(v)
  9.  
  10. def dfs_tr(v):
  11.     used[v] = True
  12.     component.push(v)
  13.     for i in range(0, len(gr[v]), 1):
  14.         if not used[gr[v][i]]:
  15.             dfs_tr(gr[v][i])
  16.            
  17. with open("in.txt") as f:
  18.     n = int(f.readline()) # число районов
  19.     inbox = {}
  20.     for i in range(1, n+1):
  21.         next = []  
  22.         for el in f.readline().split():
  23.             next.append(int(el))
  24.             inbox[i] = next
  25.     change = int(f.readline())  # номер скважины, где нужно менять направление   
  26. for arr in inbox.values():
  27.     arr.remove(arr[0]) # удалила количество скважин
  28.  
  29. changevert = [change] # чтобы легче делать разность множеств
  30. vertixes = [] # чтобы легче делать разность множеств
  31. for i in range(1, n+1):
  32.     vertixes.append(i) 
  33.  
  34. # {1: [4, 2, 3], 2: [4, 3], 3: [4], 4: []} - исходный
  35. for k in inbox:
  36.     if change in inbox[k]:
  37.         inbox[k] = list(set(inbox[k]) - set(changevert))
  38. #  {1: [3, 4], 2: [4, 3], 3: [4], 4: []}
  39.  
  40. for j in inbox[change]: # поменяла направление
  41.     inbox[int(j)].append(change)
  42. # {1: [3, 4], 2: [4, 3], 3: [4, 2], 4: [2]}
  43.  
  44. k = 0
  45. for k in inbox:
  46.     if k == change:
  47.         inbox[k] = list(set(vertixes) - set(inbox[k]))
  48.         inbox[k] = list(set(inbox[k]) - set(changevert))
  49. # {1: [3, 4], 2: [1], 3: [4, 2], 4: [2]}
  50.  
  51. outbox = inbox.copy()
  52. # получить список следующих из списка предшествующих
  53. for k in outbox:
  54.     changevert = [k]
  55.     outbox[k] = list(set(vertixes) - set(outbox[k]))
  56.     outbox[k] = list(set(outbox[k]) - set(changevert))
  57.  
  58.  
  59. # Алгоритм. Врываюсь.
  60. g = outbox
  61. gr = inbox
  62. used = []
  63. order = []
  64. component = []
  65.  
  66.  
  67. used = [n * False]
  68. for i in range(0, n, 1):
  69.     if not used[i]:
  70.         dfs(i)
  71.  
  72. used = [n * False]
  73. for i in range(0, n, 1):
  74.     v = order[n-1-i]
  75.     if not used[v]:
  76.         dfs_tr(v)
  77.         # ... вывод очередной component ...
  78.         print("component", component)
  79.         component = []
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement