Pagini recente » Cod sursa (job #1783677) | Cod sursa (job #1715816) | Cod sursa (job #950033) | Cod sursa (job #376455) | Cod sursa (job #2793006)
from collections import defaultdict
from collections import deque
class Graph:
def __init__(self, nodes):
self.numOfNodes = nodes
self.neighbours = defaultdict(list)
def addDirectedEdge(self, u, v):
self.neighbours[u].append(v)
def addUndirectedEdge(self, u, v):
self.neighbours[u].append(v)
self.neighbours[v].append(u)
def addTransposeEdge(self, u, v):
self.neighbours[v].append(u)
def deleteNodes(self, *nodes):
for node in nodes:
del self.neighbours[node]
self.numOfNodes -= 1
return self
def transpose(self):
if self.numOfNodes > 0:
transposed_graph = defaultdict(list)
for source, targets in self.neighbours.items():
for target in targets:
transposed_graph[target].append(source)
t = Graph(self.numOfNodes)
t.neighbours = transposed_graph
return t
else:
return None
def explore(self, source, visited, stack):
visited[source] = True
for node in self.neighbours[source]:
if not visited[node]:
self.explore(node, visited, stack)
stack.append(source)
def topologicalSort(self, source, visited, res):
visited[source] = True
res.append(source)
for i in self.neighbours[source]:
if not visited[i]:
self.topologicalSort(i, visited, res)
return res
def bfs(self, s):
visited = {i: False for i in range(1, self.numOfNodes + 1)}
queue = []
queue.append(s)
visited[s] = True
while queue:
s = queue.pop(0)
print(s)
for i in self.neighbours[s]:
if not visited[i]:
queue.append(i)
visited[i] = True
file = 'sortaret.in'
with open(file, 'rt') as f:
content = f.readlines()
content = [line.strip().split() for line in content]
content = [[int(x) for x in line] for line in content]
N, M = content[0][0], content[0][1]
g = Graph(N)
for edges in content[1:]:
g.addDirectedEdge(edges[0], edges[1])
visited = {i: False for i in range(1, g.numOfNodes + 1)}
result = []
result = g.topologicalSort(1, visited, result)
with open('sortaret.out', 'wt') as f:
for node in result:
f.write(str(node))
f.write(' ')