Cod sursa(job #3317161)

Utilizator NeacsaDenisDenis Neacsa NeacsaDenis Data 22 octombrie 2025 16:35:10
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 0.91 kb
# 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()