Cod sursa(job #3165106)

Utilizator flawreenFlorin Craciun flawreen Data 5 noiembrie 2023 14:14:27
Problema Parcurgere DFS - componente conexe Scor 95
Compilator py Status done
Runda Arhiva educationala Marime 0.76 kb
import sys

with open("dfs.in", "r") as f:
    global n, m, graf
    n, m = [int(x) for x in f.readline().split()]
    graf = [list() for _ in range(n + 1)]
    for ls in f.readlines():
        ls = ls.split()
        graf[int(ls[0])].append(int(ls[1]))
        graf[int(ls[1])].append(int(ls[0]))

viz = [0 for _ in range(n + 1)]
sys.setrecursionlimit(n+1)

# print("\n".join([" ".join([str(x) for x in ls]) for ls in graf]))

def df(s):
    viz[s] = 1
    for i in graf[s]:
        if viz[i] == 0:
            df(i)


def detCC():
    cc = 0
    for i in range(1, n + 1):
        if viz[i] == 0:
            df(i)
            cc += 1
    return cc


with open("dfs.out", "w") as f:
    rez = detCC()
    f.write(str(rez))
    # print(rez)