Advertisement
Guest User

Untitled

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