Cod sursa(job #2796910)

Utilizator lazarstefania63@yahoo.comLazar Stefania [email protected] Data 8 noiembrie 2021 23:42:50
Problema Componente biconexe Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 5 kb
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')