Cod sursa(job #3249190)

Utilizator cezara06cezara zamfir cezara06 Data 15 octombrie 2024 12:13:50
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.96 kb
def citire(file):
    f = open(file, 'r')

    values = f.readline()

    i = 0
    while values[i] != ' ':
        i+=1
    n = int(values[:i])
    m = int(values[i+1:])

    muchii = list()
    for line in f:
        muchii.append([int(line[0]), int(line[2])])
    
    f.close()

    return m,n,muchii

def adjList(muchii, n):
    l = {nod: set() for nod in range(n)}

    for u, v in muchii:
        l[u].add(v)   
        #pt graf neorientat
        l[v].add(u)

    return l

def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            dfs(graph, neighbour, visited)

def explore_graph(graph):
    conex_comp = 0
    visited = set()
    for node in graph:
        if node not in visited:
            dfs(graph, node,visited)
            conex_comp += 1
    print(conex_comp)

m,n,muchii = citire('date.in')
graph = adjList(muchii,n)

explore_graph(graph)