Pagini recente » Cod sursa (job #1962293) | Cod sursa (job #23509) | Cod sursa (job #2707199) | Monitorul de evaluare | Cod sursa (job #3317161)
# enunt: https://www.infoarena.ro/problema/dfs
def dfs(graph, start, visited=None):
visited[start] = True
for node in graph[start]:
if not visited[node]:
dfs(graph, node, visited)
def read_data():
with open("dfs.in", "r") as fin:
n, m = map(int, fin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
p1, p2 = map(int, fin.readline().split())
graph[p1].append(p2)
graph[p2].append(p1)
return graph
def write_data(components):
with open("dfs.out", "w") as fout:
fout.write(str(components) + "\n")
def main():
graph = read_data()
visited = [False] * len(graph)
components = 0
for node in range(1, len(graph)):
if not visited[node]:
dfs(graph, node, visited)
components += 1
write_data(components)
if __name__ == "__main__":
main()