from collections import defaultdict
from collections import deque
from queue import PriorityQueue
import filecmp
class Graph:
def __init__(self, nodes=0):
self.nodes = nodes
self.neighbours = defaultdict(list)
self.weights = {(u, v): 0 for u in range(1, self.nodes + 1) for v in range(1, self.nodes + 1)}
# adds a directed edge to graph
def addDirectedEdge(self, u, v, w=0):
self.neighbours[u].append(v)
self.weights[(u, v)] = w
# adds a directed edge to graph
def addUndirectedEdge(self, u, v, w=0):
self.neighbours[u].append(v)
self.neighbours[v].append(u)
self.weights[(u, v)] = w
def addNode(self, node):
self.nodes += 1
self.neighbours[node] = []
# 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
for key in self.weights:
if key[0] == node:
del self.weights[key]
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 and returns BFS order starting from source node and returns the path as a list
def bfs(self, source):
bfsOrder = []
visited = {i: False for i in self.neighbours.keys()}
queue = []
queue.append(source)
visited[source] = True
while queue:
current = queue.pop(0)
bfsOrder.append(current)
print(source, sep=' ')
for i in self.neighbours[current]:
if not visited[i]:
queue.append(i)
visited[i] = True
print(f"BFS starting from node {source} is:\n {bfsOrder} \n")
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 self.neighbours.keys()}
queue = []
cost = [0] * (self.nodes + 1)
queue.append(source)
visited[source] = True
while queue:
current = queue.pop(0)
# print(current, sep=' ')
for i in self.neighbours[current]:
if not visited[i]:
queue.append(i)
cost[i] = cost[current] + 1
visited[i] = True
for node in self.neighbours.keys():
if not visited[node]:
cost[node] = -1
return cost
# helper function for Tree Diameter computation
# return the index of the last Node of the longest path from source Node and the length of the path
def bfs_darb(self, source):
bfsOrder = []
distance = [-1 for i in range(self.nodes + 1)]
visited = {i: False for i in range(1, self.nodes + 1)}
queue = []
distance[source] = 1
queue.append(source)
visited[source] = True
while queue:
current = queue.pop(0)
bfsOrder.append(current)
for i in self.neighbours[current]:
if not visited[i]:
distance[i] = distance[current] + 1
queue.append(i)
visited[i] = True
maxLength = 0
nodeIndex = 0
for i in range(1, self.nodes + 1):
if distance[i] > maxLength:
maxLength = distance[i]
nodeIndex = i
# print(f"BFS starting from node {source} is:\n {bfsOrder} \n Maximum length is: {maxLength}\n")
return nodeIndex, maxLength
# returns the Diameter of a Tree and the nodes at each end
def darb(self):
node1, distance = self.bfs_darb(1)
node2, diameter = self.bfs_darb(node1)
# print(f"Diameter of tree is {diameter} calculated between nodes:\n {node1} and {node2}\n")
return node1, node2, diameter
# returns DFS traversal starting from source node as a list
# helper function for numberOfConnectedComponents
def dfs(self, source, visited, dfsOrder=[]):
visited[source] = True
dfsOrder.append(source)
for i in self.neighbours[source]:
if not visited[i]:
self.dfs(i, visited)
return dfsOrder
# 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
# helper function for finding strongly connected components
# dfs traversal; before returning push node to stack
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)
# helper function for finding strongly connected components
# counts SCC and stores each component in a dictionary
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
# helper function used in topologicalSort
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
# helper function to find cut vertices in an undirected graph
def art_p_dfs(self, source, visited, ap, parent, low_link, timestamp, time):
children = 0
visited[source] = True
timestamp[source] = time
low_link[source] = time
time += 1
for neighbour in self.neighbours[source]:
if not visited[neighbour]:
parent[neighbour] = source
children += 1
self.art_p_dfs(neighbour, visited, ap, parent, low_link, timestamp, time)
low_link[source] = min(low_link[source], low_link[neighbour])
if (parent[source] == -1 and children > 1) or (parent[source] != -1 and low_link[neighbour] >= timestamp[source]):
ap[source] = True
elif neighbour != parent[source]:
low_link[source] = min(low_link[source], timestamp[neighbour])
# returns the ARTICULATION POINTS (CUT VERTICES) in an undirected graph
def articulation_points(self):
time = 0
visited = {i: False for i in self.neighbours.keys()}
disc = {i: -1 for i in self.neighbours.keys()}
low = {i: -1 for i in self.neighbours.keys()}
parent = {i: -1 for i in self.neighbours.keys()}
ap = {i: False for i in self.neighbours.keys()}
for i in self.neighbours.keys():
if not visited[i]:
self.art_p_dfs(i, visited, ap, parent, low, disc, time)
art_points = [node for node in ap.keys() if ap[node]]
if art_points:
return art_points
else:
return None
# helper function used in bridges
def bridgesDFS(self, source, time, visited, parent, low_link, timestamp, bridges):
visited[source] = True
timestamp[source] = time
low_link[source] = time
time += 1
for neighbour in self.neighbours[source]:
if not visited[neighbour]:
parent[neighbour] = source
self.bridgesDFS(neighbour, time, visited, parent, low_link, timestamp, bridges)
low_link[source] = min(low_link[source], low_link[neighbour])
if low_link[neighbour] > timestamp[source]:
print(source, neighbour)
bridges.append([source, neighbour])
elif neighbour != parent[source]:
low_link[source] = min(low_link[source], timestamp[neighbour])
# returns the bridges in an undirected graph
def bridges(self):
time = 0
bridges = []
visited = {i: False for i in self.neighbours.keys()}
timestamp = {i: -1 for i in self.neighbours.keys()}
low_link = {i: -1 for i in self.neighbours.keys()}
parent = {i: -1 for i in self.neighbours.keys()}
for node in self.neighbours.keys():
if not visited[node]:
self.bridgesDFS(node, time, visited, parent, low_link, timestamp, bridges)
return bridges
# helper function to find Bi-connected Components of an Undirected Graph
def biconnected_c_dfs(self, source, time, visited, parent, low_link, timestamp, stack,
component_e, components_e, component_n, components_n):
children = 0
visited[source] = True
timestamp[source] = time
low_link[source] = time
time += 1
for neighbour in self.neighbours[source]:
if not visited[neighbour]:
parent[neighbour] = source
children += 1
stack.append((source, neighbour))
self.biconnected_c_dfs(neighbour, time, visited, parent, low_link, timestamp, stack, component_e, components_e, component_n, components_n)
low_link[source] = min(low_link[source], low_link[neighbour])
if (parent[source] == -1 and children > 1) or (parent[source] != -1 and low_link[neighbour] >= timestamp[source]):
edge = (None, None)
while edge != (source, neighbour):
edge = stack.pop()
component_e.append(edge)
component_n.add(edge[0])
component_n.add(edge[1])
components_e.append(component_e.copy())
component_e.clear()
components_n.append(component_n.copy())
component_n.clear()
elif neighbour != parent[source] and low_link[source] > timestamp[neighbour]:
low_link[source] = min(low_link[source], timestamp[neighbour])
stack.append((source, neighbour))
# finds Bi-connected Components of an Undirected Graph
def biconnected_components(self):
timestamp = {i: -1 for i in self.neighbours.keys()}
low_link = {i: -1 for i in self.neighbours.keys()}
parent = {i: -1 for i in self.neighbours.keys()}
visited = {i: False for i in self.neighbours.keys()}
stack = deque()
time = 0
component_e = []
components_e = []
component_n = set()
components_n = []
nodes = {}
for i in self.neighbours.keys():
if not visited[i]:
self.biconnected_c_dfs(i, time, visited, parent, low_link, timestamp, stack, component_e, components_e, component_n, components_n)
if stack:
while stack:
edge = stack.pop()
component_e.append(edge)
component_n.add(edge[0])
component_n.add(edge[1])
nodes[timestamp[edge[0]]] = edge[0]
nodes[timestamp[edge[1]]] = edge[1]
components_e.append(component_e.copy())
components_n.append(component_n.copy())
component_e.clear()
component_n.clear()
# returns nodes of every component as a set
# and returns edges of every component as list of tuples
return components_n, components_e
# helper function to find all shortest paths from source to target in undirected graph
# finds all paths with specified length from source to target
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
# helper function to find all shortest paths in undirected graph
# returns all path with specified length from source to target
def print_all_paths(self, source, target, length):
visited = {i: False for i in self.neighbours.keys()}
path = []
paths = []
self.dfs_all_paths(source, target, visited, path, paths, length)
return paths
# helper function to find all shortest paths in undirected graph
# finds parents of each node in a path
def sht_paths_bfs(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)
# helper function to find all shortest paths in undirected graph
# stores paths in reversed order starting with the last node (leaf --> root)
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()
# prints all paths from source to target
def print_paths(self, source, target):
paths = []
path = []
parent = {i: [] for i in range(1, self.nodes + 1)}
self.sht_paths_bfs(parent, source)
self.find_paths(paths, path, parent, target)
for path in paths:
path = reversed(path)
for node in path:
print(node, end=" ")
print()
# returns all shortest paths in undirected graph
def bfs_shortest_paths(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
# Dijkstra Algorithm (does not work if graph has negative cycles)
# Returns the costs from source node to every other node in the graph
def Dijkstra(self, source):
visited = {i: False for i in range(1, self.nodes + 1)}
costs = {i: float('inf') for i in range(1, self.nodes + 1)}
costs[source] = 0
pq = PriorityQueue()
pq.put((0, source))
while not pq.empty():
(dist, current_node) = pq.get()
visited[current_node] = True
for neighbour in self.neighbours[current_node]:
try:
cost = self.weights[(current_node, neighbour)]
if not visited[neighbour]:
old_cost = costs[neighbour]
new_cost = costs[current_node] + cost
if new_cost < old_cost:
pq.put((new_cost, neighbour))
costs[neighbour] = new_cost
except KeyError:
continue
# print(f"The cost of getting from node {source}, to every other node is:\n {costs}")
return costs
# Bellman-Ford Algorithm (works if graph has negative cycles)
# Returns the costs from source node to every other node in the graph
def Bellman_Ford(self, source):
costs = {i: float('inf') for i in range(1, self.nodes + 1)}
costs[source] = 0
for i in range(1, self.nodes + 1):
for edge, cost in self.weights.items():
if costs[edge[0]] + cost < costs[edge[1]]:
costs[edge[1]] = costs[edge[0]] + cost
for edge, cost in self.weights.items():
if costs[edge[0]] + cost < costs[edge[1]]:
costs[edge[0]] = float("-inf")
return costs
# Floyd Warshall Algorithm
# Finds all shortest(lowest cost) paths between every pair of nodes in a graph
def Floyd_Warshall(self, costs):
# input data states that if there is no path between nodes i and j, cost[i][j] = 0
# to calculate the minimum cost we need to make cost[i][j] = infinity if there is no path between nodes i and j
for i in range(len(costs[0])):
for j in range(len(costs[0])):
if i == j:
costs[i][j] = 0
elif costs[i][j] == 0:
costs[i][j] = float("inf")
else:
continue
for k in range(0, self.nodes):
for i in range(0, self.nodes):
for j in range(0, self.nodes):
costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])
return costs
# helper function for finding MAXIMUM FLOW from source to target through a network with EDMONDS KARP ALGORITHM
def ed_k_bfs(self, target, Capacity, rCapacity, parent, mFlow, queue):
while queue:
node = queue.pop(0)
for neighbour in self.neighbours[node]:
# print(node, neighbour, Capacity[(node, neighbour)], rCapacity[(node, neighbour)])
if Capacity[(node, neighbour)] - rCapacity[(node, neighbour)] > 0 and parent[neighbour] == -1:
parent[neighbour] = node
mFlow[neighbour] = min(mFlow[node], Capacity[(node, neighbour)] - rCapacity[(node, neighbour)])
if neighbour != target:
queue.append(neighbour)
else:
return mFlow[target], parent
return 0, parent
# initialize capacity matrix of graph for maximum flow tasks
def initialize_capacity_matrix(self):
Capacity = defaultdict()
for u in range(1, self.nodes + 1):
for v in range(1, self.nodes + 1):
if (u, v) in self.weights.keys():
Capacity[(u, v)] = self.weights[(u, v)]
else:
Capacity[(u, v)] = 0
return Capacity
# returns MAXIMUM FLOW from source to target through a network with EDMONDS KARP ALGORITHM
def Edmonds_Karp(self, source, target):
flow = 0
rCapacity = {(u, v): 0 for u in range(1, self.nodes + 1) for v in range(1, self.nodes + 1)}
Capacity = self.initialize_capacity_matrix()
while True:
parent = {i: -1 for i in range(1, self.nodes + 1)}
parent[source] = -2
mFlow = {i: 0 for i in range(1, self.nodes + 1)}
mFlow[source] = float("inf")
queue = [source]
path_flow, parent = self.ed_k_bfs(target, Capacity, rCapacity, parent, mFlow, queue)
if path_flow == 0:
break
flow += path_flow
node = target
while node != source:
parent_node = parent[node]
rCapacity[(parent_node, node)] = rCapacity[(parent_node, node)] + path_flow
rCapacity[(node, parent_node)] = rCapacity[(node, parent_node)] - path_flow
node = parent_node
return flow, rCapacity
# returns number of edges (and edges as list of node pairs)
# that need to be added in an undirected graph for it to become connected
def conexidad(self):
m_extra = 0
visited = {i: False for i in range(1, self.nodes + 1)}
count = 0
components = []
for node in range(1, self.nodes + 1):
if not visited[node]:
component = self.dfs(node, visited)
components.append(component.copy())
component.clear()
count += 1
components.sort(key=len, reverse=True)
extras = {i: PriorityQueue() for i in range(count)}
edges = []
for i in range(count):
for node in components[i]:
extras[i].put((0, node))
i = 0
while count > 1:
count -= 1
extra_edges1, node1 = extras[i].get()
extra_edges2, node2 = extras[i + 1].get()
extras[i].put((extra_edges1 + 1, node1))
extras[i + 1].put((extra_edges2 + 1, node2))
edges.append((node1, node2))
components[1].extend(components[0])
components.pop(0)
# print(count, components)
while not extras[i].empty():
# print(extras[i].get())
extras[i + 1].put(extras[i].get())
del extras[i]
i += 1
keys = list(extras.keys())
while not extras[keys[0]].empty():
m_extra = extras[keys[0]].get()[0]
return m_extra, edges
# MARMELADA https://www.infoarena.ro/problema/marmelada
# returns the weight of each edge of a undirected graph so that the path from SOURCE to TARGET is the shortest
def marmelada(self, source, target, edges, lengths):
lengths.sort()
paths = self.bfs_shortest_paths(source, target)
sh_path = paths[0]
for i in range(len(sh_path) - 1):
try:
edges[(sh_path[i], sh_path[i+1])].add(lengths[0])
lengths.pop(0)
except ValueError:
edges[(sh_path[i+1], sh_path[i])].add(lengths[0])
lengths.pop(0)
for key in edges.keys():
if len(edges[key]) == 0:
edges[key].add(lengths[0])
lengths.pop(0)
return edges
# MARMELADA https://www.infoarena.ro/problema/marmelada
# returns the weight of each edge of a undirected graph so that the path from SOURCE to TARGET is the shortest
def marmelada2(self, source, target, edges, lengths):
queue = []
visited = {i: False for i in self.neighbours.keys()}
queue.append([source])
visited[source] = True
while queue:
path = queue.pop(0)
node = path[-1]
if node == target:
for i in range(len(path) - 1):
try:
edges[(path[i], path[i + 1])].add(lengths[0])
lengths.pop(0)
except ValueError:
edges[(path[i + 1], path[i])].add(lengths[0])
lengths.pop(0)
for key in edges.keys():
if len(edges[key]) == 0:
edges[key].add(lengths[0])
lengths.pop(0)
return edges
for current_node in self.neighbours[node]:
if not visited[current_node]:
visited[current_node] = True
new_path = list(path)
new_path.append(current_node)
queue.append(new_path)
# PAMANT https://www.infoarena.ro/problema/pamant
# returns minimum node and the cut vertices of each connected component of a undirected graph
def pamant(self):
visited = {i: False for i in range(1, self.nodes + 1)}
components = []
art_points = []
for node in range(1, self.nodes + 1):
if not visited[node]:
component = self.dfs(node, visited)
components.append(component.copy())
component.clear()
codes = [min(c) for c in components]
for component in components:
c_graph = Graph(len(component))
for node in component:
c_graph.neighbours[node] = self.neighbours[node]
ap = c_graph.articulation_points()
if ap is not None:
art_points.append(*ap)
return codes, art_points
# # TRANSPORT2 https://www.infoarena.ro/problema/transport2
def transport2(self, source, target, visited, max_weight, dfsOrder):
pq = PriorityQueue()
visited[source] = True
if source == target:
dfsOrder.append(source)
return -max(max_weight), dfsOrder
visited[source] = True
dfsOrder.append(source)
for i in self.neighbours[source]:
if not visited[i]:
pq.put((-self.weights[(source, i)], i))
m_weight, node = pq.get()
max_weight. append(m_weight)
self.transport2(node, target, visited, max_weight, dfsOrder)
return -max(max_weight), dfsOrder
# # SENAT https://www.infoarena.ro/problema/senat
# file = 'senat.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[1][0]
#
#
# commissions = [i for i in range(N + 1, N + M + 1)]
# senators = content[2:]
#
# g = Graph(N + M)
#
# for i in range(M):
# for j in range(len(senators[i])):
# g.addUndirectedEdge(senators[i][j], commissions[i], 1)
#
# s = N + M + 1
# g.addNode(s)
#
# t = N + M + 2
# g.addNode(t)
#
# for senator in range(1, N + 1):
# g.addUndirectedEdge(s, senator, 1)
#
# for commission in range(N + 1, N + M + 1):
# g.addUndirectedEdge(commission, t, 1)
#
# check_commissions = []
# res = g.Edmonds_Karp(s, t)[1]
#
# with open('senat.out', 'wt') as f:
# for key, value in res.items():
# if value == 1 and (s not in key and t not in key):
# check_commissions.append(key[1])
# f.write(str(key[0]))
# f.write('\n')
#
# if set(check_commissions) != set(commissions):
# f.write('0')
# # TRANSPORT2 https://www.infoarena.ro/problema/transport2
# file = 'transport2.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.addUndirectedEdge(edges[0], edges[1], edges[2])
#
# visited = {i: False for i in g.neighbours.keys()}
# max_weight = []
# dfsOrder = []
#
# result = g.transport2(1, N, visited, max_weight, dfsOrder)
# print(result)
#
# with open('transport2.out', 'wt') as f:
# f.write(str(result[0]))
# MAXFLOW https://www.infoarena.ro/problema/maxflow
file = 'maxflow.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.addUndirectedEdge(edges[0], edges[1], edges[2])
result = g.Edmonds_Karp(1, N)
with open('maxflow.out', 'wt') as f:
f.write(str(result[0]))
# f1 = 'grader_test10_maxflow.ok'
# f2 = 'maxflow.out'
#
# with open(f1) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f1, 'w') as f_output:
# f_output.write(data)
#
# with open(f2) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f2, 'w') as f_output:
# f_output.write(data)
#
# print(filecmp.cmp(f1, f2))
#
#
# # PAMANT https://www.infoarena.ro/problema/pamant
# file = 'pamant.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)
# g.neighbours = {i: [] for i in range(1, g.nodes + 1)}
# for edges in content[1:]:
# g.addUndirectedEdge(edges[0], edges[1])
#
# codes, art_points = g.pamant()
# art_points.sort()
#
# with open('pamant.out', 'wt') as f:
# f.write(str(len(codes)))
# f.write('\n')
# for t_code in codes:
# f.write(str(t_code))
# f.write(' ')
# f.write('\n')
# f.write(str(len(art_points)))
# f.write('\n')
# for node in art_points:
# f.write(str(node))
# f.write(' ')
#
#
# # MARMELADA https://www.infoarena.ro/problema/marmelada
# file = 'marmelada.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, S, D = content[0][0], content[0][1], content[0][2], content[0][3]
#
# edges = defaultdict(set)
# lengths = []
# g = Graph(N)
# for e in content[1:-1]:
# g.addUndirectedEdge(e[0], e[1])
# edges[(e[0], e[1])] = set()
# # print("edges: ", edges)
#
# for length in content[-1]:
# lengths.append(length)
# # print("lengths: ", lengths)
#
# # result = g.marmelada(S, D, edges, lengths)
# # print(result)
#
# result = g.marmelada2(S, D, edges)
# print(result)
#
# with open('marmelada.out', 'wt') as f:
# for e in content[1:-1]:
# f.write(str(result[(e[0], e[1])].pop()))
# f.write('\n')
#
#
#
# # CONEXIDAD https://www.infoarena.ro/problema/conexidad
# file = 'conexidad.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.addUndirectedEdge(edges[0], edges[1])
#
# max_extra, edges = g.conexidad()
# # print(max_extra, edges)
#
# with open('conexidad.out', 'wt') as f:
# f.write(str(max_extra))
# f.write('\n')
# f.write(str(len(edges)))
# f.write('\n')
# for edge in edges:
# f.write(str(edge[0]))
# f.write(' ')
# f.write(str(edge[1]))
# f.write('\n')
# # Find distance from source to all reachable nodes in oriented graph
# file = 'bfs.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, S = content[0][0], content[0][1], content[0][2]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addDirectedEdge(edges[0], edges[1])
#
# result = g.bfs_cost(S)[1:]
#
# with open('bfs.out', 'wt') as f:
# for c in result[0:-1]:
# f.write(str(c))
# f.write(' ')
# f.write(str(result[-1]))
# # 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.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.addUndirectedEdge(edges[0], edges[1])
#
# result = g.numberOfConnectedComponents()
#
# with open('dfs.out', 'wt') as f:
# f.write(str(result))
#
#
#
# # NUMBER OF SHORTEST PATHS BETWEEN 2 NODES OF UNDIRECTED GRAPH
# file = 'graf.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, source, target = content[0][0], content[0][1], content[0][2], content[0][3]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addUndirectedEdge(edges[0], edges[1])
#
#
# r = g.bfs_shortest_paths(source, target)
# print(r)
#
# r = [set(s) for s in r]
# result = set.intersection(*r)
# print(result)
#
# with open('graf.out', 'wt') as f:
# f.write(str(len(result)))
# f.write('\n')
# for element in result:
# f.write(str(element))
# f.write(' ')
#
#
#
# # DIJKSTRA ALGORITHM
# file = 'grader_test2_dijkstra.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], edges[2])
#
# result = g.Dijkstra(1)
#
# with open('dijkstra.out', 'wt') as f:
# for node in result.keys():
# if node == 1:
# continue
#
# if result[node] == float("inf"):
# f.write(str(0))
# f.write(' ')
# else:
# f.write(str(result[node]))
# f.write(' ')
#
# f1 = 'grader_test2_dijkstra.ok'
# f2 = 'dijkstra.out'
#
# with open(f1) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f1, 'w') as f_output:
# f_output.write(data)
#
# with open(f2) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f2, 'w') as f_output:
# f_output.write(data)
#
# print(filecmp.cmp(f1, f2))
#
#
#
# # BELLMAN-FORD ALGORITHM
# file = 'grader_test10_Algoritmul_Bellman_Ford.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], edges[2])
#
# result = g.Bellman_Ford(1)
#
# with open('bellmanford.out', 'wt') as f:
# if float("-inf") in result.values():
# f.write("Ciclu negativ!")
# else:
# for cost in list(result.values()):
# if cost != 0:
# f.write(str(cost))
# f.write(' ')
#
# f1 = 'grader_test10_Algoritmul_Bellman_Ford.ok'
# f2 = 'bellmanford.out'
#
# with open(f1) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f1, 'w') as f_output:
# f_output.write(data)
#
# with open(f2) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f2, 'w') as f_output:
# f_output.write(data)
#
# print(filecmp.cmp(f1, f2))
#
#
#
# # FLOYD-WARSHALL
# file = 'grader_test3_royfloyd.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 = content[0][0]
# costs = content[1:]
#
#
# g = Graph(N)
# result = g.Floyd_Warshall(costs)
#
# with open('royfloyd.out', 'wt') as f:
# for i in range(0, g.nodes):
# for j in range(0, g.nodes):
# f.write(str(result[i][j]))
# f.write(' ')
# f.write('\n')
#
# f1 = 'grader_test3_royfloyd.ok'
# f2 = 'royfloyd.out'
#
# with open(f1) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f1, 'w') as f_output:
# f_output.write(data)
#
# with open(f2) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f2, 'w') as f_output:
# f_output.write(data)
#
# print(filecmp.cmp(f1, f2))
#
#
#
# # TREE DIAMETER (DARB)
# file = 'darb.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 = content[0][0]
#
# g = Graph(N)
# for edges in content[1:]:
# g.addUndirectedEdge(edges[0], edges[1])
#
# result = g.darb()
#
# with open('darb.out', 'wt') as f:
# f.write(str(result[2]))
#
#
#
# # BICONNECTED COMPONENTS https://www.infoarena.ro/problema/biconex
# file = 'grader_test6_biconex.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.addUndirectedEdge(edges[0], edges[1])
#
# result = g.biconnected_components()[0]
# # print(result)
#
# with open('biconex.out', 'wt') as f:
# f.write(str(len(result)))
# f.write('\n')
# for component in result:
# for node in component:
# f.write(str(node))
# f.write(' ')
# f.write('\n')
#
# f1 = 'grader_test6_biconex.ok'
# f2 = 'biconex.out'
#
# with open(f1) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f1, 'w') as f_output:
# f_output.write(data)
#
# with open(f2) as f_input:
# data = f_input.read().rstrip('\n')
#
# with open(f2, 'w') as f_output:
# f_output.write(data)
#
# print(filecmp.cmp(f1, f2))
Andrei Sturzu Andrei_Sturzu