Pagini recente » Cod sursa (job #3367107) | Cod sursa (job #3367054) | Cod sursa (job #3367123) | Cod sursa (job #3367120) | Cod sursa (job #3367139)
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()