グラフ(union-find,クルーズ)

互いに集合する。

2つの

共通要素のない集合.

使用する2つの関数.

union-find関数

find関数(ルートノードを検索する関数)

オペレーションプロセス

union演算を確認し、2つの相互接続ノードA,Bを決定する.
-1.AとBのルートノードA',B'をそれぞれ検索する.
-2.AをBに設定した親ノード.(親ノードの場合は、より少ない設定を親ノードとします.)

すべての演算が処理されるまで繰り返します.最も必要な変数は.親ノードを表すリストが必要です.
.ルートノードを探すために、親ノードを再帰的に遡ることができます.

def find_parent(parent, x):
    if parent[x] != x:
        find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b
        
node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i

for i in range(edge_num):
    A, B = map(int, input().split())
    union(parent, A, B)

find関数:現在のノードのルートノードを位置決めします.
親リスト:親ノードの真上にあります.

経路圧縮技術。

find関数で再帰を利用すると複雑さに多くの時間がかかります.
これを補うために、親ノードを表す親リストを更新します.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

判別サイクル。

各幹線

をチェックし、2つのノードのルートノードをチェックします.
-1.ルートノードが異なる場合はunion演算を実行する
-2.互いに同じであれば周期が発生する.

手順

1を繰り返します.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b

node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i
# 다른 부분은 동일 하지만
# 아래 부분만 다르다.
# 부모 노드가 같은 경우엔 브레이크 하고 바로 나간다.
-------------------------------------------------------------------------------------------------
cycle = False

for i in range(edge_num):
    A, B = map(int, input().split())
    if find_parent(parent, A) == find_parent(parent, B):
        cycle = True
        break
    else:
        union(parent, A, B)
-------------------------------------------------------------------------------------------------

ストレッチツリー

身長木とは何ですか.
1つのグラフィックには、すべてのノードが含まれ、ループが存在しない部分があります.

クルースカ

最低コストで伸びた木を探します.
最も重要なのは、すべての幹線をソートすることです.

オペレーションプロセス

幹線データはコスト増でソートされます.

本線を点検し、周期が発生しているか確認する
−1.最小伸長木に含まれるサイクルX
-2.サイクルOは、最小身長ツリーには含まれません.

すべての幹線に対して

を2回繰り返します.

常に成立しており,伸長木に含まれる幹線の数は「ノードの個数−1」である.△もちろんです.
ex)7ノードに接続するには6本の幹線が必要です.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return x

def union(parent, a, b):
    root_a = find_parent(parent, a)
    root_b = find_parent(parent, b)
    if root_a < root_b:
        parent[b] = root_a
    else:
        parent[a] = root_b

node, edge_num = map(int, input().split())
parent = [0] * (node + 1)

for i in range(len(parent)):
    parent[i] = i

edges = []
results = 0

for i in range(edge_num):
    A, B, cost = map(int, input().split())
    edges.append((cost, A, B))
    
# 정렬을 수행.
# 루트 노드들이 다른 것의 경우 사이클이 발생하지 않는다.
# 그러한 노드들 만을 모아 결과를 출력
-------------------------------------------------------------------------------------------------    
edges.sort()

for item in edges:
    cost, a, b = item
    if find_parent(parent, a) != find_parent(parent, b):
        results += cost
        union(parent, a, b)

print(results)
-------------------------------------------------------------------------------------------------

位相位置合わせ

一連のタスクを順番に実行するアルゴリズム.(方向性に反するものではないことを示す)
方向性があるため、ノードには入力回数があります.
進入車数は?
特定のノードに入る幹線の個数を意味します.
入る回数を表示するリストが必要です
ガイドと呼びましょう.

オペレーションプロセス

アクセス数0のノードをキューに入れます.

キューがリクエストを発行するまで、次の手順を繰り返します.
-1.キューから要素を取り出し、そのノードから出発する幹線をグラフィックから削除します.
-2.新規アクセス数0のノードをキューに入れます.

すべての要素にアクセスする前にキューが空の場合、ループが存在します.(描いて解決しましょう.
入場回数が0未満ではキューに入れません.ループがある場合は0になりません.

from _collections import deque

node, edge_num = map(int, input().split())
#진입차수의 초기화가 필요하다 
indegree = [0] * (node + 1)
graph = [[] for i in range(node + 1)]

for _ in range(node):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
def topology_sort():
    #정렬된 값들을 담을 리스트
    result = []
    q = deque()
    
    #진입차수가 0인 것을 큐에 담기.
    for idx, item in enumerate(indegree):
        if not item:
            q.append(idx)
    
    while q:
        now = q.popleft()
        result.append()
        for data in graph[now]:
            indegree[data] -= 1
            if not indegree[data]:
                q.append(data)

    for i in result:
        print(i, end=" ")
    
topology_sort()