Cod sursa(job #2449723)

Utilizator voyagerSachelarie Bogdan voyager Data 20 august 2019 15:50:58
Problema Componente tare conexe Scor 30
Compilator py Status done
Runda Arhiva educationala Marime 1.22 kb
#!/usr/bin/env python3

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

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

with open('ctc.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])

    idx, stk, ctc = 0, [], []

    def dfs(v):
        global idx

        v.idx = v.minIdx = idx
        idx += 1
        stk.append(v)
        v.onStack = True

        for vv in v.edges:
            if vv.idx is None:
                dfs(vv)
                v.minIdx = min(v.minIdx, vv.minIdx)
            elif vv.onStack:
                v.minIdx = min(v.minIdx, vv.idx)

        if v.idx == v.minIdx:
            s = []
            while True:
                vv = stk.pop()
                vv.onStack = False
                s.append(vv.lbl)
                if vv == v:
                    break
            ctc.append(' '.join(s))

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

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