Cod sursa(job #2796263)

Utilizator lazarstefania63@yahoo.comLazar Stefania [email protected] Data 7 noiembrie 2021 20:07:27
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 1.51 kb
adj_list = {}
my_list = []


def add_node(node):
    if node not in my_list:
        my_list.append(node)


def add_edge(node1, node2):
    temp = []
    if node1 in my_list and node2 in my_list:
        if node1 not in adj_list:
            temp.append(node2)
            adj_list[node1] = temp
        elif node1 in adj_list:
            temp.extend(adj_list[node1])
            temp.append(node2)
            adj_list[node1] = temp


def dfs(starting_node):
    visited, stack, result = {starting_node}, [starting_node], []
    while stack:
        node = stack.pop()
        print(node)
        result.append(node)
        if node in adj_list:
            for n in reversed(adj_list[node]):
                if n not in visited:
                    stack.append(n)
                    visited.add(n)
    return visited


def graph():
    for node in adj_list:
        print(node, " ---> ", [i for i in adj_list[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)
        add_edge(y, x)
    return n, m


visit = []
connected = 0
f = open("dfs.in", "r")
f_out = open("dfs.out", "w")
N, M = read()


for nod in range(1, N + 1):
    if nod not in visit:
        connected += 1
        result_dfs = dfs(nod)
        for each_node in result_dfs:
            visit.append(each_node)


f_out.write(str(connected))