Cod sursa(job #3165111)

Utilizator flawreenFlorin Craciun flawreen Data 5 noiembrie 2023 14:23:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator py Status done
Runda Arhiva educationala Marime 0.87 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)]

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


def df(s):
    stk = list()
    stk.append(s)
    while len(stk) > 0:
        s = stk.pop()

        if viz[s] == 0:
            viz[s] = 1

        for x in graf[s]:
            if viz[x] == 0:
                stk.append(x)


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)