[ baekjoon ] 1976. 旅行に行こう

質問する

ドンヒョクは友達と一緒に旅行に行きます.韓国にはN都市があり、任意の2都市の間に道があるかもしれないし、道がないかもしれない.東赫の旅行日程が決まったとき、この旅行ルートができるかどうか見てみましょう.もちろん、途中で他の都市を経由して旅行することもできます.例えば、5つの都市があり、A-B、B-C、A-D、B-D、E-Aの道があり、東赫の旅行計画がE-CBCDであれば、E-A-B-C-B-C-B-Dという旅行経路で目的を達成することができる.
都市の個数と都市とのつながり、東ヒョクの観光計画の都市が順番に並ぶかどうかを決めるプログラムを作成します.同じ都市を何度も訪問できる.

入力

1行目は都市の数Nを与える.Nは200以下である.2行目は旅行計画に属する都市の数Mを与えた.Mは1000以下です.次のN行にはN個の整数がある.i 1行目のj個数は、i番都市とj番都市との接続情報を表す.1は接続されていることを示し、0は接続されていないことを示します.AとBがつながって、BとAもつながった.最後の列は旅行計画を示した.都市番号は1からNの順に並んでいます.

しゅつりょく

1行目が可能ならYESが不可能ならNO出力

import sys  
input = sys.stdin.readline

n = int(input())
m = int(input())

# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
  if parent[x] != x: # 자기 자신이 아닌 경우, 루트 노드 존재
    parent[x] = find_parent(parent, parent[x]) # 루트노드
  return parent[x]

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

graph = [[] for _ in range(n)]
for i in range(n):
  info = list(map(int, input().split()))
  for j in range(len(info)):
    graph[i].append(info[j])

parent = [0] * n # 부모 테이블 초기화

# 부모를 자기 자신을 초기화
for i in range(n):
  parent[i] = i

for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      union_parent(parent, i, j) # 집합 합치기

# 여행 경로 입력 받기
plan = list(map(int, input().split()))

root = find_parent(parent, plan[0] - 1)
check = True

# 여행 경로에 대한 모든 root 확인
for p in plan:
  if not root == find_parent(parent, p - 1):
     check = False
     break 

# 모든 여행 경로에 대해 root가 같으면 YES
print('YES' if check else 'NO')

UnionFind問題-コメントリンク
繰り返し可能なため、DFS/BFSアルゴリズムを使用して解凍するとメモリがオーバーフローします.
図アレイに接続されているポイント(1)はunion関数を使用してコレクションをマージします.
その後,すべての旅行経路についてルートノードが同じでなければ旅行計画を行うことができない.

フロイドウォーシェル

Flowersalアルゴリズムで記述されたコード

n = int(input())  # 총 도시의 수
m = int(input())  # 여행 계획에 속한 도시들의 수
graph = [list(map(int, input().split())) for _ in range(n)]
plan = list(map(int, input().split()))

# 플로이드-워셜 알고리즘을 통해 모든 노드 간의 최소 거리를 구한다.
for i in range(n):
    for j in range(n):
        if graph[i][j] == 0 and i != j:  # 길이 없는 경우
            graph[i][j] = 1e9  # 10억으로 대입

# 최소 거리 갱신
for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 여행 여부 확인
check = True
prev = plan[0] - 1
for i in range(1, m):
    if graph[prev][plan[i] - 1] >= 1e9:  # 길이 없는 경우
        check = False
        break
    else:
        prev = plan[i] - 1

if check:
    print("YES")
else:
    print("NO")

最初はBFSアルゴリズムで解きましたがメモリオーバーフロー、、、
私はあなたがよく考えていると思って、ほほほ.ははは….他にも問題かもしれませんが、

メモリオーバーフローエンクロージャ（BFSアルゴリズム）

import sys    
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n)]
for i in range(n):
  info = list(map(int, input().split()))
  for j in range(len(info)):
    if info[j] == 1:
      graph[i].append(info[j])

plan = list(map(int, input().split()))

def bfs(start):
  idx = 1
  q = deque([start])
  while q:
    city = q.popleft()
    for i in graph[city]:
      if plan[idx] - 1 == i:
        idx += 1
        if idx == m - 1:
          return True
      q.append(i)
  return False

if bfs(plan[0] - 1):
  print('YES')
else:
  print('NO')

21.04.17復習

## 1976 여행 가자
import sys  
input = sys.stdin.readline

n = int(input())
m = int(input())

parent = [0] * n

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

def union_parent(a, b):
  a = find_parent(a)
  b = find_parent(b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
    
for i in range(n):
  parent[i] = i # 자기 자신으로 초기화

for i in range(n):
  arr = list(map(int, input().split()))
  for j in range(n):
    if arr[j] == 1:
      if find_parent(i) != find_parent(j):
        union_parent(i, j)

plan = list(map(int, input().split()))

comp = 0
for i in range(len(plan)):
  if i == 0:
    comp = parent[plan[0] - 1]
  elif parent[plan[i] - 1] != comp:
    print("NO")
    exit(0)
print("YES")

union-findを思い出しました
index errorは10回現れましたハハ

for i in range(n):
  arr = list(map(int, input().split()))
  for j in range(n):
    if arr[j] == 1:
      if find_parent(i) != find_parent(j):
        union_parent(i, j)

union parent中

for i in range(n):

乙、乙

for i in range(m):

書く...
インデックスエラー
またfind parent()メソッド定義も間違っています.

def find_parent(a):
  if parent[a] != a:
    return find_parent(parent[a])
  else:
    return a

これによりparent配列はリフレッシュされません.
気をつけてね.