Pagini recente » Borderou de evaluare (job #2349488) | Borderou de evaluare (job #2338461) | Cod sursa (job #2797278)
import copy
import random
adj_list = {}
trans_adj_list = {}
my_list = []
def add_node(node):
if node not in my_list:
my_list.append(node)
def add_edge(node1, node2, my_graph):
temp = []
if node1 in my_list and node2 in my_list:
if node1 not in my_graph:
temp.append(node2)
my_graph[node1] = temp
elif node1 in my_graph:
temp.extend(my_graph[node1])
temp.append(node2)
my_graph[node1] = temp
def dfs(my_graph, starting_node):
stack, result = [starting_node], []
while stack:
node = stack.pop()
if node in result:
continue
result.append(node)
if node in my_graph:
for n in my_graph[node]:
stack.append(n)
return result
def read():
n, m = [int(x) for x in f.readline().split()]
for i in range(1, n + 1):
add_node(i)
for i in range(m):
x, y = [int(z) for z in f.readline().split()]
add_edge(x, y, adj_list) # graph is oriented
add_edge(y, x, trans_adj_list) # transpose graph
return n, m
def remove_key(my_graph, delete_value):
if delete_value in my_graph:
del my_graph[delete_value]
for edges in my_graph.values():
copy_edge = copy.deepcopy(edges)
if delete_value in copy_edge:
edges.remove(delete_value)
ctc = []
f = open("ctc.in", "r")
f_out = open("ctc.out", "w")
N, M = read()
while adj_list:
nod = random.choice(list(adj_list.keys()))
result_dfs = dfs(adj_list, nod)
trans_result_dfs = dfs(trans_adj_list, nod)
plus_minus = list(set(result_dfs) & set(trans_result_dfs))
ctc.append(plus_minus)
for member in plus_minus:
remove_key(adj_list, member)
remove_key(trans_adj_list, member)
f_out.write(str(len(ctc)))
f_out.write('\n')
for x in ctc:
f_out.write(" ".join(str(y) for y in x))
f_out.write('\n')