Cod sursa(job #2795827)

Utilizator NSA-16Neacsu-Tranciuc Sasa-Andrei NSA-16 Data 7 noiembrie 2021 01:12:58
Problema Componente biconexe Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 1.68 kb
import sys
sys.setrecursionlimit(10 ** 6)
def biconex(file, file2):
    import collections
    f = open(file, "r")
    g = open(file2, "w")
    n, m = [int(n) for n in f.readline().split()]
    d = [[] for _ in range(n + 1)]
    for i in range(m):
        n1, n2 = [int(n) for n in f.readline().split()]
        d[n1].append(n2)
        d[n2].append(n1)
    ids = (n+1)*[0]
    lowlink = (n+1)*[0]
    parent = (n+1)*[0]
    biconex = []
    stack = collections.deque()
    nid = collections.deque()
    def DFS(n):
        nid.append(0)
        ids[n] = len(nid)
        lowlink[n] = len(nid)
        for i in d[n]:
            if ids[i] == 0:
                haschild = True
                parent[i] = n
                stack.append((n, i))
                DFS(i)
                lowlink[n] = min(lowlink[n], lowlink[i])
                if (parent[n] == 0 and haschild) or (parent[n] != 0 and lowlink[i] >= ids[n]):
                    k = stack.pop()
                    c = {k[0]}
                    while k != (n, i):
                        k = stack.pop()
                        c.add(k[0])
                    if len(c) > 1:
                        biconex.append(sorted(c))
                    else:
                        c.add(k[1])
                        biconex.append(sorted(c))
            elif parent[n] != i and lowlink[n] > ids[i]:
                lowlink[n] = ids[i]
                stack.append((n, i))
    for i in range(1, n + 1):
        if ids[i] == 0:
            DFS(i)
    g.write(str(len(biconex)))
    for c in biconex:
        g.write('\n'+" ".join(str(n) for n in c))
    f.close()
    g.close()
biconex("biconex.in", "biconex.out")