Cod sursa(job #2449850)

Utilizator voyagerSachelarie Bogdan voyager Data 20 august 2019 21:06:35
Problema Componente biconexe Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 1.69 kb
#!/usr/bin/env python3

import sys
sys.stdout = open('biconex.out', 'w')

class Node(object):
    def __init__(self, lbl):
        self.lbl = lbl
        self.idx = None
        self.minIdx = None
        self.edges = []

with open('biconex.in', 'r') as f:
    pair = lambda: tuple(map(int, f.readline().split()))

    N, M = pair()
    nodes = [Node(str(i + 1)) for i in range(N)]
    for _ in range(M):
        A, B = pair()
        nodes[A - 1].edges.append(nodes[B - 1])
        nodes[B - 1].edges.append(nodes[A - 1])

    idx, stk, solStk, compos = 0, [], [], []

    def dfs(v):
        global idx
        v.idx = v.minIdx = idx
        idx += 1
        stk.append(v)

        while stk:
            v = stk[-1]

            while v.edges:
                vv = v.edges.pop()
                if vv.idx is None:
                    vv.idx = vv.minIdx = idx
                    idx += 1
                    stk.append(vv)
                    solStk.append((v, vv))
                    break
                else:
                    v.minIdx = min(v.minIdx, vv.idx)

            if v == stk[-1]:
                v = stk.pop()
                if stk:
                    stk[-1].minIdx = min(stk[-1].minIdx, v.minIdx)
                    if stk[-1].idx <= v.minIdx:
                        s = []
                        while True:
                            a, b = solStk.pop()
                            s.append(b.lbl)
                            if a == stk[-1]:
                                s.append(a.lbl)
                                break
                        compos.append(' '.join(s))

    for v in nodes:
        if v.idx is None: dfs(v)

    print(len(compos))
    for x in compos:
        print(x)