Cod sursa(job #3367139)

Utilizator mihaisoare349Soare Mihai-Alexandru mihaisoare349 Data 6 octombrie 2026 11:21:45
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.32 kb
import dataclasses
from collections.abc import Iterator


@dataclasses.dataclass(frozen=True)
class Node:
    id: int
    adj: list[Node] = dataclasses.field(default_factory=list)

    def dfs(self) -> Iterator[Node]:
        visited = set()

        def recurse(n: Node):
            if n in visited:
                return
            visited.add(n)

            yield n
            for x in n.adj:
                yield from recurse(x)

        yield from recurse(self)

    def __eq__(self, value: object, /) -> bool:
        return isinstance(value, Node) and self.id == value.id

    def __hash__(self) -> int:
        return hash(self.id)


def main():
    nodes = read()

    def connected_components():
        visited = set()

        while len(visited) < len(nodes):
            starting_point = next(n for n in nodes if n not in visited)
            component = set(starting_point.dfs())
            yield component
            visited |= component

    print(sum(1 for _ in connected_components()))


def read() -> list[Node]:
    n, m = map(int, input().split())
    nodes = [Node(i) for i in range(1, n + 1)]

    for _ in range(m):
        src, dest = map(int, input().split())
        nodes[src - 1].adj.append(nodes[dest - 1])
        nodes[dest - 1].adj.append(nodes[src - 1])

    return nodes


if __name__ == "__main__":
    main()