Pagini recente » Cod sursa (job #1862222) | Cod sursa (job #2140103) | Cod sursa (job #923793) | Cod sursa (job #2817243) | Cod sursa (job #2796910)
import copy
import random
adj_list = {}
my_list = []
back_edge = {}
bi_con = []
articulation_node = []
def add_node(node):
if node not in my_list:
my_list.append(node)
def add_edge(node1, node2, edge):
temp = []
if node1 in my_list and node2 in my_list:
if node1 not in edge:
temp.append(node2)
edge[node1] = temp
elif node1 in edge:
temp.extend(edge[node1])
temp.append(node2)
edge[node1] = sorted(temp)
def add_edge_dfs(node1, node2):
temp = [node1, node2]
dfs_edge.append(temp)
def original_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 bi_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 reversed(my_graph[node]):
# stack.append(n)
# return result
def find_dfs_edges():
idx = 0
visited = set()
while idx < len(res) - 1:
nod1 = res[idx]
nod2 = res[idx + 1]
if nod2 in adj_list[nod1]:
if nod2 not in visited:
add_edge_dfs(nod1, nod2)
visited.add(nod2)
# add_edge(nod2, nod1, dfs_edge)
else:
for nod3 in reversed(res[0:idx]):
if nod2 in adj_list[nod3]:
if nod2 not in visited:
add_edge_dfs(nod3, nod2)
visited.add(nod2)
# add_edge(nod2, nod3, dfs_edge)
idx += 1
# def find_back_edges():
# for nod in adj_list:
# for edge in adj_list[nod]:
# if edge not in dfs_edge[nod]:
# add_edge(nod, edge, back_edge)
def graph():
for node in adj_list:
print(node, " ---> ", [i for i in adj_list[node]])
def graph1():
for node in dfs_edge:
print(node)
def graph2():
for node in back_edge:
print(node, " ---> ", back_edge[node])
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)
add_edge(y, x, adj_list)
return n, m
def remove_key(dic, delete_value):
new_dic = copy.deepcopy(dic)
for nodes in dic.keys():
if nodes == delete_value:
del new_dic[nodes]
for edges in new_dic.values():
if delete_value in edges:
edges.remove(delete_value)
return new_dic
def find_articulation_node():
visit = []
connected = 0
for nod in my_list:
if nod not in visit:
connected += 1
result_dfs = original_dfs(adj_list, nod)
for each_node in result_dfs:
visit.append(each_node)
visit_new = []
connected_new = 0
new_list = copy.deepcopy(my_list)
new_list.remove(nod)
new_adj_list = remove_key(adj_list, nod)
for nod2 in new_list:
if nod2 not in visit_new:
connected_new += 1
result_dfs = original_dfs(new_adj_list, nod2)
for each_node in result_dfs:
visit_new.append(each_node)
if connected != connected_new:
articulation_node.append(nod)
f = open("biconex.in", "r")
f_out = open("biconex.out", "w")
N, M = read()
dfs_edge = []
# start = random.randint(1, N)
# print(start)
res = original_dfs(adj_list, 1)
find_dfs_edges()
# find_back_edges()
find_articulation_node()
find_bi_comp = set()
for edge in dfs_edge:
found = 0
for element_bi in bi_con:
if element_bi[-1] == edge[0]:
found = 1
if edge[0] in articulation_node and edge[1] in articulation_node:
bi_con.append(edge)
elif edge[0] in articulation_node:
if len(adj_list[edge[1]]) > 1:
element_bi.append(edge[1])
else:
bi_con.append(edge)
elif edge[1] in articulation_node:
if element_bi[0] in adj_list[edge[1]]:
element_bi.append(edge[1])
elif len(adj_list[edge[1]]) > 1:
element_bi.append(edge[1])
else:
bi_con.append(edge)
else:
element_bi.append(edge[1])
if found == 0:
bi_con.append(edge)
f_out.write(str(len(bi_con))+'\n')
for comp in bi_con:
for nod in comp:
f_out.write(str(nod) + ' ')
f_out.write('\n')