Cod sursa(job #2506804)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 8 decembrie 2019 19:52:39
Problema Componente tare conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 3.93 kb
#Longest Palindromic Subsequence
#Overlapping Subprolems property.
"""def lps(seq,i,j):
    if i==j:
        return 1
    if seq[i]==seq[j] and j==i+1:
        return 2
    if seq[i]==seq[j]:
        return lps(seq,i+1,j-1)+2
    return max(lps(seq,i,j-1),lps(seq,i+1,j))

seq="GEEKSFORGEEKS"
n= len(seq)
print(lps(seq,0,n-1))"""

"""seq="GEEKSFORGEEKS"
n= len(seq)
L=[[0 for x in range(n)] for x in range(n)]
for i in range(n):
    L[i][i]=1
for lp in range(2,n+1):
    for inc in range(n-lp+1):
        sf=inc+lp-1
        if seq[inc]==seq[sf] and sf==inc+1:
            L[inc][sf]=2
        elif seq[inc]==seq[sf]:
            L[inc][sf]=L[inc+1][sf-1]+2
        else:
            L[inc][sf]=max(L[inc+1][sf],L[inc][sf-1])
print(L[0][n-1])"""

"""c1={"Darius":[10,8],"Florin":[2]}
c2={"Darius":[10],"Florin":[10,10,10]}
a1={"Florin":2,}
a2={"Darius":1,"Florin":2}
rez=dict()

def max(list):
    ans=-100
    for i in list:
        if i>ans:
            ans=i
    return ans

#c1["Darius"].remove(max(c1["Darius"]))
#print(c1["Darius"])

for x in a1.keys():
    if x in c1.keys():
        for i in range(min(a1[x],len(c1[x]))):
            M=max(c1[x])
            c1[x].remove(M)
        if len(c1[x]):
            rez[x]=c1[x]
        else:
            rez[x]=[2]
    else:
        rez[x]=[1]

for x in c1.keys():
    if x not in a1.keys():
        rez[x]=c1[x]
#print(rez)

for x in a2.keys():
    if x in c2.keys():
        for i in range(min(a2[x] ,len(c2[x]))):
            M = max(c2[x])
            c2[x].remove(M)
            #print(M)
        if len(c2[x]):
            rez[x]+=c2[x]
    else:
        rez[x]+=[1]

for x in c2.keys():
    if x not in a2.keys():
        rez[x]=c2[x]
#print(rez)

def medie(l):
    ans=0
    for i in l:
        ans+=i
    ans/=len(l)
    return ans

rez={x:medie(rez[x]) for x in rez.keys()}
print(rez)
"""

from collections import defaultdict
import sys
class graph:
    def __init__(self,v):
        self.V=v
        self.graph=defaultdict(list)
        self.order=0
        self.comp=0
        self.rez=defaultdict(list)
    def add_Edge(self,a,b):
        self.graph[a].append(b)
    def dfs(self,x,low,din,sol,viz):
        din[x]=self.order  #ordinea normala din dfs
        low[x]=din[x]
        self.order+=1
        viz[x]=True
        sol.append(x)
        #print(x)
        for i in self.graph[x]:
            if din[i]==-1:
                self.dfs(i,low,din,sol,viz)
                low[x]=min(low[x],low[i])
            elif viz[i]==True:
                low[x]=min(low[x],din[i])
        if din[x]==low[x]:
            y=-1
            while y!=x:
                y=sol.pop()
                #print(y,end="")
                #print(',',end="")
                self.rez[self.comp].append(y)
                viz[y]=False
            self.comp += 1

    def solve(self):
        din=list()
        low=list()
        viz=list()
        for i in range(0,self.V+1):
            din.append(-1)
            low.append(-1)
            viz.append(False)
        sol=[]
        for i in range(1,self.V+1):
            if din[i]==-1:
                self.dfs(i,low,din,sol,viz)

    def show(self):
        with open("ctc.out","w") as g:
            g.write(str(self.comp))
            g.write('\n')
            for i in range(0,self.comp+1):
                #self.rez[i]=sorted(self.rez[i])
                for j in self.rez[i]:
                    g.write(str(j))
                    g.write(' ')
                g.write('\n')

with open("ctc.in","r") as f:
    sys.setrecursionlimit(10000)
    s=f.readline().replace('\n','').split(' ')
    n=int(s[0])
    m=int(s[1])
    G=graph(n)
    for i in range(0,m):
        t=f.readline().replace('\n','').split(' ')
        a=int(t[0])
        b=int(t[1])
        G.add_Edge(a,b)
        #print(a,b)
    G.solve()
    G.show()