微商产品做网站,seo推广一年要多少钱,网络营销论文1500字,怎样编辑网站看见题目知道时间复杂度不超过#xff08;mlogm#xff09;。
这题用强连通分量 Tarjan 算法#xff0c;强联通#xff1a;对于任意两个点u和v#xff0c;u可以到达v#xff0c;v也可以到达u。这题需要考虑有重边#xff0c;自环#xff0c;同样别忘记可能会有两个点u…
看见题目知道时间复杂度不超过mlogm。
这题用强连通分量 Tarjan 算法强联通对于任意两个点u和vu可以到达vv也可以到达u。这题需要考虑有重边自环同样别忘记可能会有两个点u和vu不能到达vv也不能到达u的情况就是u和v不在同一个图中数据中会存在几个图的情况。
Tarjan 算法主要是维护两个列表dnf和lowdnf[i]记录到达i这个点的次序low记录i这个点的祖先次序。如果dnf[i]low[i]就是说i这个点就是祖先节点如果dnf[i] ! low[i]那么i这个点是某个祖先节点的儿子。
洛谷超时一个还有待改进。
遇到一个问题就是需要考虑数据中存在不同的图
from collections import defaultdict, dequedef taij(node):global idxdfn[node] idxlow[node] idxidx 1stack.append(node)v[node] 1vis[node] 1for nex in edge[node]:if vis[nex] 0:taij(nex)low[node] min(low[node], low[nex])elif v[nex]:low[node] min(low[node], dfn[nex])if dfn[node] low[node]:ls []while dfn[stack[-1]] ! dfn[node]:nex stack.pop()ls.append(nex1)v[nex] 0nex stack.pop()v[nex] 0ls.append(nex1)ls sorted(ls[::-1])ans.append(ls)n, m map(int, input().split())
edge defaultdict(list)
dfn [0]*n
low [0]*n
stack deque()
v [0]*n
vis [0]*n
idx 0
ans []
for _ in range(m):uu, vv map(int, input().split())edge[uu-1].append(vv-1)
taij(0)
for i in range(n):if vis[i] 0:taij(i)leth len(ans)
print(leth)
ans.sort()
for i in range(leth):for j in ans[i]:print(j, end )print()
