宝石收集，tarjan

本文主要是介绍宝石收集，tarjan，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0宝石收集 - 蓝桥云课 (lanqiao.cn)

n=int(input())
s='0'+input()
m=int(input())
mp=[[] for i in range(n+1)]
for i in range(m):a,b=map(int,input().split())a+=1b+=1mp[a].append(b)import sys
sys.setrecursionlimit(100000000)
dfn=[0 for i in range(n+1)]
low=[0 for i in range(n+1)]
cnt=0stk=[]
instk=[0 for i in range(n+1)]p=0
scc=[0 for i in range(n+1)]def tarjan(x):global cnt,pcnt+=1dfn[x]=low[x]=cntstk.append(x)instk[x]=1for i in mp[x]:if dfn[i]==0:tarjan(i)low[x]=min(low[x],low[i])elif instk[i]:low[x]=min(low[x],dfn[i])if dfn[x]==low[x]:p+=1y=stk.pop()instk[y]=0scc[y]=pwhile x!=y:y = stk.pop()instk[y] = 0scc[y] = p
for i in range(1,n+1):if dfn[i]==0:tarjan(i)del instk,low,dfnru=[0 for i in range(p+1)]
h=[0 for i in range(p+1)]
l=[0 for i in range(p+1)]
nmp=[[] for i in range(p+1)]
for i in range(1,n+1):if s[i]=='0': h[scc[i]]+=1else : l[scc[i]]+=1for j in mp[i]:if scc[i]!=scc[j]:ru[scc[j]]+=1nmp[scc[i]].append(scc[j])
del mpdef dfs(x,a,b):ans=0vis=0for y in nmp[x]:ans=max(dfs(y,a+h[y],b+l[y]),ans)vis=1if vis==0:return min(a,b)else:return ans
ans=0
for i in range(1,p+1):if ru[i]==0:ans=max(ans,dfs(i,h[i],l[i]))
print(ans)

这篇关于宝石收集，tarjan的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---