Cod sursa(job #2788820)

Utilizator lazarstefania63@yahoo.comLazar Stefania [email protected] Data 26 octombrie 2021 15:00:36
Problema Parcurgere DFS - componente conexe Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.54 kb
class Node:
    def __init__(self, val):
        self.val = val
        self.edges = []


class Graph:

    def __init__(self, nodes=None):
        if nodes is None:
            nodes = []
        self.nodes = nodes

    def add_node(self, val):
        new_node = Node(val)
        self.nodes.append(new_node)

    def add_edge(self, node1, node2):
        node1.edges.append(node2)
        node2.edges.append(node1)

    def dfs(self, starting_node):
        if not self.nodes:
            return []
        start = self.nodes[starting_node-1]
        visited, stack, result = {start}, [start], []
        while stack:
            node = stack.pop()
            result.append(node)
            for n in node.edges:
                if n not in visited:
                    stack.append(n)
                    visited.add(n)
        return result


graph = Graph()
f = open("dfs.in", "r")
f_out = open("dfs.out", "w")
N, M = [int(x) for x in f.readline().split()]

for i in range(1, N + 1):
    graph.add_node(i)
for i in range(M):
    x, y = [int(z) for z in f.readline().split()]
    for n0 in graph.nodes:
        for n1 in graph.nodes:
            if n0.val == x and n1.val == y:
                graph.add_edge(n0, n1)
                break

connected = set()
node = [z for z in range(1, N + 1)]

for component in node:
    dfs_result = graph.dfs(component)
    connected.add(tuple(dfs_result))
    for j in range(len(dfs_result)):
        node.remove(dfs_result[j].val)

f_out.write(str(len(connected)+len(node)))