from main.memorare_graf import memorareListaAdiacenta
def memorareListaAdiacenta(fileName, orientat = False):
    vectorMuchii = []
    for linie in open(fileName, "r").read().strip().split("\n"):
        vectorMuchii.append(linie.split(" "))
    aux = vectorMuchii.pop(0)
    nrNoduri = int(aux.pop(0))
    nrMuchii = int(aux.pop(0))
    graf = [[] for i in range(nrNoduri + 1)]
    if orientat is True:
        for muchie in vectorMuchii:
            graf[int(muchie[0])].append(int(muchie[1]))
    else:
        for muchie in vectorMuchii:
            graf[int(muchie[0])].append(int(muchie[1]))
            graf[int(muchie[1])].append(int(muchie[0]))
    return graf

def dfs(start, graf):
    visited = [False for i in range(len(graf))]
    dfsOut = [start]
    stack = [start]
    visited[start] = True
    nodCurent = start
    while stack != []:
        for element in graf[nodCurent]:
            if visited[element] is False:
                stack.append(element)
                visited[element] = True
                dfsOut.append(element)
        nodCurent = stack.pop(-1)
    return dfsOut

def componenteConexe(graf):
    visited = [False for i in range(len(graf))]
    contor = 0
    for i in range(1,len(graf)):
        if visited[i] is False:
            temp = dfs(i,graf)
            for element in temp:
                visited[element] = True
            contor += 1
    return contor

graf = memorareListaAdiacenta("../DFS/dfs.in")

print(componenteConexe(graf))