(실버 II) 알고리즘 클래스 – 깊이 우선 검색 6 – 24484

분류

그래프 이론, 그래프 순회, 정렬, 깊이 우선 순회

문제 설명

지금도 서준은 깊이 우선 탐색(DFS) 과정을 가르치고 있습니다.

아버지가 가르친 내용을 학생들이 이해했는지 질문으로 확인해 봅시다.

N개의 정점을 가짐 M개의 모서리로 구성된 무방향 그래프가 주어집니다.

정점 번호 매기기는 1부터 시작합니다.

N번, 모든 모서리의 가중치는 1입니다.

최고 수준의 R부터 시작하여 깊이 우선 검색으로 구축된 트리를 깊이 우선 검색 트리라고 가정합니다.

깊이 우선 검색 트리에서 노드 i의 깊이 디라고 하자.정점 시작 R의 깊이는 0이고 방문하지 않은 노드의 깊이는 -1입니다.

최고 수준의 R로 시작하는 경우 깊이 우선 검색을 통해 노드를 방문하십시오. 노드 i를 방문한 순서 티타늄이라고합시다.

시작 정점의 방문 순서는 1이고 시작 정점에서 방문할 수 없는 노드는 0입니다.

모든 노드에 대해 떨어지다 엑스 티탄 값의 합을 알아봅시다.

깊이 우선 검색의 의사 코드는 다음과 같습니다.

내림차순방문하다

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited(R) <- YES;  # 시작 정점 R을 방문 했다고 표시한다.


    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 내림차순으로 방문한다)
        if (visited(x) = NO) then dfs(V, E, x);
}

입력하다

첫 번째 행의 정점 수 아니요 (5≤ 아니요 ≤ 100,000), 변의 수 쌀 (1≤ 쌀 ≤ 200,000), 시작 정점 아르 자형 (1≤ 아르 자형 ≤ 나) 주어집니다.

다음 M 라인의 에지 정보 주어진 uv, 정점 정점과 당신 v에 대한 가중치가 1인 양방향 에지를 나타냅니다.

(1≤ 너 < V ≤ , 너 ≠ v) 모든 모서리(u, v) 쌍의 값이 다릅니다.

인쇄

첫 번째 행의 모든 노드에 대해 떨어지다 엑스 티탄 출력 값의 합계입니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M, R = map(int, input().split())
graph = (() for _ in range(N + 1))

for _ in range(M):
    u, v = map(int, input().split())
    graph(u).append(v)
    graph(v).append(u)


def DFS(r):
    global flag
    idx = sorted(graph(r), reverse=True)
    for i in idx:
        if visited(i) == 0:
            visited(i) = 1
            flag += 1
            T(i) = flag
            D(i) = D(r) + 1
            DFS(i)
            

D = (-1) * (N + 1)
T = (0) * (N + 1)
visited = (0) * (N + 1)

D(R) = 0
T(R) = 1
visited(R) = 1

flag = 1
DFS(R)

result = 0
for j in range(1, N + 1):
    result += D(j) * T(j)

print(result)