Cod sursa(job #3317863)

Utilizator ciprianvlad02@gmail.comvlad ciprian [email protected] Data 25 octombrie 2025 18:10:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator py Status done
Runda Arhiva educationala Marime 1.97 kb
'''
filein = open("adiacenta.in", "r")
fileout = open("adiacenta.out", "w")

n, m = [int(x) for x in filein.readline().split()] # n = nr noduri, m = nr muchii
matrice = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    a, b = [int(x) for x in filein.readline().split()]
    matrice[a-1][b-1] = 1
    matrice[b-1][a-1] = 1
    
for linie in matrice:
    print(*linie, file=fileout)

'''

#trec prin toate nodurile si verific daca in lista lor de inamici se afla si inamicul celui cerut de mn sau daca ei sunt inamici

'''

n, m = map(int, input().split())
enemies = [[] for _ in range(n + 1)]  # folosim 1-based indexing

for _ in range(m):
    query = input().split()
    if query[0] == '+':
        v, u = int(query[1]), int(query[2])
        enemies[v].append(u)
    elif query[0] == '?':
        v = int(query[1])
        friends = set()

        # Pentru fiecare inamic al lui v
        for e in enemies[v]:
            # pentru fiecare inamic al inamicului e
            for f in enemies[e]:
                if (
                    f != v and                # nu poate fi el însuși
                    f not in enemies[v]       # nu trebuie să fie inamic direct
                ):
                    friends.add(f)

        print(len(friends))

'''

with open("dfs.in", "r") as filein, open("dfs.out", "w") as fileout:
    n, m = map(int, filein.readline().split())
    vecini = [[] for _ in range(n + 1)]

    for _ in range(m):
        x, y = map(int, filein.readline().split())
        vecini[x].append(y)
        vecini[y].append(x)

    visited = set()
    k = 0

    def dfs_iterative(start):
        stack = [start]
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                stack.extend(vecini[node])

    for i in range(1, n + 1):
        if i not in visited:
            dfs_iterative(i)
            k += 1

    fileout.write(str(k))