当前位置: 首页> 汽车> 新车 > 宝石收集,tarjan

宝石收集,tarjan

时间:2025/7/11 8:00:14来源:https://blog.csdn.net/m0_64675532/article/details/139222148 浏览次数: 0次

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: