Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python3
- # def main():
- # чтение файла, biparted = {номер множества[1..n] : [элементы множества]}
- def dfs(v):
- used[v] = True
- for i in range(0, len(g[v]), 1):
- if not used[g[v][i]]:
- dfs(g[v][i])
- order.push(v)
- def dfs_tr(v):
- used[v] = True
- component.push(v)
- for i in range(0, len(gr[v]), 1):
- if not used[gr[v][i]]:
- dfs_tr(gr[v][i])
- with open("in.txt") as f:
- n = int(f.readline()) # число районов
- inbox = {}
- for i in range(1, n+1):
- next = []
- for el in f.readline().split():
- next.append(int(el))
- inbox[i] = next
- change = int(f.readline()) # номер скважины, где нужно менять направление
- for arr in inbox.values():
- arr.remove(arr[0]) # удалила количество скважин
- changevert = [change] # чтобы легче делать разность множеств
- vertixes = [] # чтобы легче делать разность множеств
- for i in range(1, n+1):
- vertixes.append(i)
- # {1: [4, 2, 3], 2: [4, 3], 3: [4], 4: []} - исходный
- for k in inbox:
- if change in inbox[k]:
- inbox[k] = list(set(inbox[k]) - set(changevert))
- # {1: [3, 4], 2: [4, 3], 3: [4], 4: []}
- for j in inbox[change]: # поменяла направление
- inbox[int(j)].append(change)
- # {1: [3, 4], 2: [4, 3], 3: [4, 2], 4: [2]}
- k = 0
- for k in inbox:
- if k == change:
- inbox[k] = list(set(vertixes) - set(inbox[k]))
- inbox[k] = list(set(inbox[k]) - set(changevert))
- # {1: [3, 4], 2: [1], 3: [4, 2], 4: [2]}
- outbox = inbox.copy()
- # получить список следующих из списка предшетсвующих
- for k in outbox:
- changevert = [k]
- outbox[k] = list(set(vertixes) - set(outbox[k]))
- outbox[k] = list(set(outbox[k]) - set(changevert))
- # Алгоритм. Врываюсь.
- g = outbox
- gr = inbox
- used = []
- order = []
- component = []
- used = [n * False]
- for i in range(0, n, 1):
- if not used[i]:
- dfs(i+1)
- used = [n * False]
- for i in range(0, n, 1):
- v = order[n - 1 - i]
- if not used[v - 1]:
- dfs_tr(v)
- # ... вывод очередной component ...
- print("component", component)
- component = []
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement