from collections import defaultdict
from collections import deque
class Graph:
def __init__(self, nodes):
self.nodes = nodes
self.neighbours = defaultdict(list)
self.time = 0
# adds a directed edge to graph
def addDirectedEdge(self, u, v):
self.neighbours[u].append(v)
# adds a directed edge to graph
def addUndirectedEdge(self, u, v):
self.neighbours[u].append(v)
self.neighbours[v].append(u)
# deletes nodes that have the ids mentioned in nodes list
def deleteNodes(self, *nodes):
for node in nodes:
del self.neighbours[node]
self.nodes -= 1
return self
# creates the transposed graph
def transpose(self):
if self.nodes > 0:
transposed_graph = defaultdict(list)
for source, targets in self.neighbours.items():
for target in targets:
transposed_graph[target].append(source)
t = Graph(self.nodes)
t.neighbours = transposed_graph
return t
else:
return None
# prints BFS order starting from source node and returns the path as a list
def bfs(self, source):
bfsOrder = []
visited = {i: False for i in range(1, self.nodes + 1)}
queue = []
queue.append(source)
visited[source] = True
while queue:
source = queue.pop(0)
bfsOrder.append(source)
print(source, sep=' ')
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
visited[i] = True
return bfsOrder
# returns the minimum number of arches needed to get from source to every other node in the graph
# if there is no path the value will be -1
def bfs_cost(self, source):
visited = {i: False for i in range(1, self.nodes + 1)}
queue = []
cost = {i: 0 for i in range(1, self.nodes + 1)}
queue.append(source)
visited[source] = True
while queue:
source = queue.pop(0)
print(source, sep=' ')
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
cost[i] = cost[source] + 1
visited[i] = True
for node in self.neighbours.keys():
if not visited[node]:
cost[node] = -1
return cost
# returns DFS order starting from source node and returns the path as a list
def dfs(self, source, visited):
print(source)
visited[source] = True
for i in self.neighbours[source]:
if not visited[i]:
self.dfs(i, visited)
return visited
# returns number of connected componets in an undirected graph
def numberOfConnectedComponents(self):
visited = {i: False for i in range(1, self.nodes + 1)}
count = 0
for node in range(1, self.nodes + 1):
if not visited[node]:
self.dfs(node, visited)
count += 1
return count
def dfs_Kosaraju1(self, source, visited, stack):
visited[source] = True
for node in self.neighbours[source]:
if not visited[node]:
self.dfs_Kosaraju1(node, visited, stack)
stack.append(source)
def dfs_Kosaraju2(self, source, visited, components, count):
visited[source] = True
components[count].append(source)
transpose_g = self.transpose()
for node in transpose_g.neighbours[source]:
if not visited[node]:
self.dfs_Kosaraju2(node, visited, components, count)
# returns the strongly connected components in a directed graph
def SCC_Kosaraju(self):
stack = deque()
components = defaultdict(list)
count = 0
visited = {i: False for i in range(1, self.nodes + 1)}
for node in list(self.neighbours.keys()):
if not visited[node]:
self.dfs_Kosaraju1(node, visited, stack)
visited = {i: False for i in range(1, self.nodes + 1)}
while stack:
node = stack.pop()
if not visited[node]:
count += 1
self.dfs_Kosaraju2(node, visited, components, count)
return components
def topoSortDFS(self, soruce, visited, stack):
visited[soruce] = True
for neighbour in self.neighbours[soruce]:
if not visited[neighbour]:
self.topoSortDFS(neighbour, visited, stack)
stack.append(soruce)
# returns a topological sort of the nodes of a directed graph
def topologicalSort(self):
stack = deque()
result = []
visited = {i: False for i in range(1, self.nodes + 1)}
for node in list(self.neighbours.keys()):
if not visited[node]:
self.topoSortDFS(node, visited, stack)
while stack:
node = stack.pop()
result.append(node)
return result
def bridgesDFS(self, u, visited, parent, low_link, timestamp, bridges):
visited[u] = True
timestamp[u] = self.time
low_link[u] = self.time
self.time += 1
for v in self.neighbours[u]:
if not visited[v]:
parent[v] = u
self.bridgesDFS(v, visited, parent, low_link, timestamp, bridges)
low_link[u] = min(low_link[u], low_link[v])
if low_link[v] > timestamp[u]:
print(u, v)
bridges.append((u, v))
elif v != parent[u]:
low_link[u] = min(low_link[u], timestamp[v])
# returns and prints the bridges in an undirected graph
def bridges(self):
bridges = []
visited = [False] * (self.nodes + 1)
timestamp = [-1] * (self.nodes + 1)
low_link = [-1] * (self.nodes + 1)
parent = [-1] * (self.nodes + 1)
for node in range(1, self.nodes + 1):
if not visited[node]:
self.bridgesDFS(node, visited, parent, low_link, timestamp, bridges)
return bridges
# prints BFS order starting from source node and returns the path as a list
def bfs_shortest_path(self, source, target):
visited = {i: False for i in range(1, self.nodes + 1)}
distance = [float('inf')] * (self.nodes + 1)
number_of_paths = [0] * (self.nodes + 1)
queue = []
distance[source] = 0
number_of_paths[source] = 1
queue.append(source)
visited[source] = True
s = source
while queue:
source = queue.pop(0)
for i in self.neighbours[source]:
if not visited[i]:
queue.append(i)
visited[i] = True
if distance[i] > distance[source] + 1:
distance[i] = distance[source] + 1
number_of_paths[i] = number_of_paths[source]
elif distance[i] == distance[source] + 1:
number_of_paths[i] += number_of_paths[source]
paths = self.print_all_paths(s, target, distance[target])
return paths
def dfs_all_paths(self, source, target, visited, path, paths, length):
visited[source] = True
path.append(source)
if source == target:
if len(path) - 1 == length:
paths.append(path.copy())
else:
for i in self.neighbours[source]:
if not visited[i]:
self.dfs_all_paths(i, target, visited, path, paths, length)
path.pop()
visited[source] = False
def print_all_paths(self, source, target, length):
visited = {i: False for i in range(1, self.nodes + 1)}
path = []
paths = []
self.dfs_all_paths(source, target, visited, path, paths, length)
return paths
def bfs_all_shortest_paths(self, parent, source):
distance = [float('inf')] * (self.nodes + 1)
q = deque()
q.append(source)
parent[source] = [-1]
distance[source] = 0
while q:
currentNode = q[0]
q.popleft()
for neighbour in self.neighbours[currentNode]:
if distance[neighbour] > distance[currentNode] + 1:
distance[neighbour] = distance[currentNode] + 1
q.append(neighbour)
parent[neighbour].clear()
parent[neighbour].append(currentNode)
elif distance[neighbour] == distance[currentNode] + 1:
parent[neighbour].append(currentNode)
def find_paths(self, paths, path, parent, target):
if target == -1:
paths.append(path.copy())
return
for par in parent[target]:
path.append(target)
self.find_paths(paths, path, parent, par)
path.pop()
def print_paths(self, source, target):
paths = []
path = []
parent = {i: [] for i in range(1, self.nodes + 1)}
self.bfs_all_shortest_paths(parent, source)
self.find_paths(paths, path, parent, target)
for path in paths:
path = reversed(path)
for node in path:
print(node, end=" ")
print()
return paths
# # STRONGLY CONNECTED COMPONENTS
# file_ctc = 'ctc.in'
#
# with open(file_ctc, '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.nodes + 1)}
# result = g.SCC_Kosaraju()
#
# with open('ctc.out', 'wt') as f:
# f.write(str(len(result.keys())))
# f.write('\n')
# for component in result.values():
# for node in component:
# f.write(str(node))
# f.write(' ')
# f.write('\n')
# # TOPOLOGICAL SORT
# file_sortaret = 'sortaret.in'
#
# with open(file_sortaret, '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, N + 1)}
#
# result = g.topologicalSort()
#
# with open('sortaret.out', 'wt') as f:
# for node in result:
# f.write(str(node))
# f.write(' ')
# # NUMBER OF CONNECTED COMPONENTS
# file_dfs = 'dfs.in'
#
# with open(file_dfs, '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.addUndirectedEdge(edges[0], edges[1])
#
# result = g.numberOfConnectedComponents()
#
# with open('dfs.out', 'wt') as f:
# f.write(str(result))
# n = 4
# connections = [[0,1],[1,2],[2,0],[1,3]]
# n = 8
# connections = [[0, 1], [0, 3], [1, 2], [3, 4], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [6, 7]]
# connections = [(a+1, b+1) for (a, b) in connections]
# print(connections)
# n = 4
# connections = [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]
#
# g = Graph(n)
# for edges in connections:
# g.addUndirectedEdge(edges[0], edges[1])
#
# print(g.bfs_shortest_path(1, 4))
# NUMBER OF SHORTEST PATHS BETWEEN 2 NODES OF UNDIRECTED GRAPH
# file_dfs = 'graf.in'
#
# n = 5
# g = Graph(n)
# g.addDirectedEdge(1, 3)
# g.addDirectedEdge(2, 3)
# g.addDirectedEdge(2, 5)
# g.addDirectedEdge(4, 2)
# g.addDirectedEdge(4, 5)
#
# print("BFS:")
# result = g.bfs_cost(4)
# print(result)
#
# print("DFS:")
# visited = {i: False for i in range(1, n+1)}
# result = g.dfs(4, visited)
#
# print("Topological sort:")
# print(g.topologicalSort())
file = 'ctc.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 list(g.neighbours.keys())}
result = g.SCC_Kosaraju()
with open('ctc.out', 'wt') as f:
f.write(str(count))
f.write('\n')
for component in result.values():
for node in component:
f.write(str(node))
f.write(' ')
f.write('\n')
Tiganus Alexandru redikus