CCF-201509-4-고속도로

이 문제는 강연통분량을 찾고 그림의 모든 강연통분량을 찾으며 각 분량의 도시 대수를 계산하여 답을 얻어야 한다는 것이 분명하다.도시 쌍을 계산하는 방법은 강연통분량의 결점수*(강연통분량의 결점-1)/2
python 코드:

import sys

sys.setrecursionlimit(10 ** 7)


def tarjan(u):
    global idx
    global bcnt
    idx += 1
    dfn[u] = low[u] = idx
    stack.append(u)
    in_stack[u] = True

    for v in graph[u]:
        if not dfn[v]:
            tarjan(v)  # dfs(v)
            low[u] = min(low[u], low[v])  #   
        elif in_stack[v]:
            low[u] = min(low[u], dfn[v])

    #    ，  dfn[u] == low[u]， u      
    if dfn[u] == low[u]:
        sccs[bcnt] = []
        while True:
            v = stack.pop()
            in_stack[v] = False
            sccs[bcnt].append(v)
            if u == v:
                break
        bcnt += 1


n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    from_n, to_n = [int(e) - 1 for e in input().split()]
    graph[from_n].append(to_n)

#       ，        ，0      ，  0     
dfn = [0] * n

#        
low = [0] * n

#     
idx = 0

stack = []

#        
in_stack = [False] * n

#       
sccs = {}

#        
bcnt = 0

for i in range(n):
    if not dfn[i]:
        tarjan(i)

ans = 0
for v in sccs.values():
    cnt = len(v)
    ans += int(cnt / 2 * (cnt - 1))
print(ans)

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CCF-201509-4-고속도로

이 문제는 강연통분량을 찾고 그림의 모든 강연통분량을 찾으며 각 분량의 도시 대수를 계산하여 답을 얻어야 한다는 것이 분명하다.도시 쌍을 계산하는 방법은 강연통분량의 결점수*(강연통분량의 결점-1)/2 python ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CCF-201509-4-고속도로

좋은 웹페이지 즐겨찾기