[ baekjoon ] 11724. 接続要素の数

13183 ワード
DFS/BFS algorithm 最短パス baekjoon テキストリンク
11724.接続要素の数
質問する
方向図があるかどうかは、接続要素の数を計算するプログラムを作成します.
入力
第1行は、頂点の個数Nと、幹線の個数Mとを与える.(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N−1)/2)2行目から、幹線の両端点uおよびvがM行に与えられる.(1≦u,v≦N,u≠v)のような幹線は一度しか与えられない.
しゅつりょく
接続要素の数を最初の行に出力します.
接続要素とは、無方向図で2つの異なる頂点がパスで接続されていることを意味します.
親シェイプに他の頂点がない部分を表すシェイプ
接続要素になる条件
1.エレメント内のすべての頂点を接続するパスが必要です.
2.他の接続要素に属する頂点に接続するパスは使用できません.
DFSアルゴリズムを用いたコードは多い.
クルーズアルゴリズムでソースコードを書きました
  • DFSアルゴリズム
    • を追加
    UNION
    ## 11724_연결요소의 개수
import sys
input = sys.stdin.readline
n, m = map(int, input().split())

graph = []
for _ in range(m):
  a, b = map(int, input().split())
  if a > b: # 첫번째 정점 번호를 작게 만듬
    a, b = b, a
  graph.append((a, b)) 

parent = [0] * (n + 1)
for i in range(n + 1):
  parent[i] = i

def find_parent(parent, a): # 특정 원소가 속핮 집합 찾기
  if parent[a] != a:
    parent[a] = find_parent(parent, parent[a])
  return parent[a]

def union_parent(parent, a, b): # 집합 합치기
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  parent[b] = a

graph.sort()

before = 0
# 간선 하나씩 확인
for edge in graph: 
  a, b = edge
  if before == find_parent(parent, a): # 처리됐던 번호(a)와 같으면 pass
    union_parent(parent, before, b)
    pass
  elif before == find_parent(parent, b):
    union_parent(parent, before, a)
    pass
  else: # 부모가 바뀌지 않았으면
    before = find_parent(parent, a)
    union_parent(parent, a, b) # 집합 합치기

print(len(set(parent)) - 1) 
# 첫번째 원소가 0이기 때문에 이것을 제외한 집합 개수 찾기
    DFS
    import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for _ in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visited = [False] * (n + 1)
def dfs(v):
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      dfs(i)

result = 0

for i in range(1, n + 1):
  if not visited[i]:
    dfs(i)
    result += 1

print(result)
    pythonは再帰制限に関連しており、再帰許容値を超えた場合、実行時エラーが発生します.
    ->sys.setrecursionlimitの作成(10000)
    基本的には1000です
    ウィーチャットで写真を撮られるとページが更新されるバグに苦しめられて気が狂う
    Android EditText表情(文字列)をカーソル位置に挿入