Cod sursa(job #3317861)

Utilizator ciprianvlad02@gmail.comvlad ciprian [email protected] Data 25 octombrie 2025 18:06:44
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 2.18 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))

'''

filein = open("dfs.in", "r")
fileout = open("dfs.out", "w")

n, m = map(int, filein.readline().split()) # n = nr noduri, m = nr muchii

vecini = [[] for _ in range(n + 1)]  # 1-based adjacency lists

def dfs(vecini, node, visited=None):
    if visited is None:
        visited = set()
    if node not in visited:
        visited.add(node)
        for neighbor in vecini[node]:
            dfs(vecini, neighbor, visited)

# read edges and store neighbors as 1-based indices
for _ in range(m):
    x, y = map(int, filein.readline().split())
    if y not in vecini[x]:
        vecini[x].append(y)
    if x not in vecini[y]:
        vecini[y].append(x)

# run DFS for each component using a shared visited set
visited = set()
k=0
for i in range(1, n + 1):
    if i not in visited:
        dfs(vecini, i, visited)
        k= k+1


fileout.write(str(k))
filein.close()
fileout.close()