BOJ 10451シーケンス周期
8086 ワード
https://www.acmicpc.net/problem/10451
1秒、256 MBメモリ
input : T N (2 ≤ N ≤ 1,000) 整数 output : シーケンスに存在するシーケンス周期数 隣接するノードはそれぞれ1つしかありません.
各ノードの隣接ノードを整理する.
```python
graph = [0]
data = list(map(int, sys.stdin.readline().split()))
for item in data:
graph.append(item)
```
図[0]には、隣接ノードが1から始まり、1から始まるように0が追加されている.
どうやって彼らを組み合わせますか?
ルートノード方式を使用します.
root[now]=root[next node]の場合、ループです.
隣接ノードを解決するのは自分の場合です.
DFSの挙動は.
visit[start]から処理を開始し、
ルートがnext nodeと異なる場合
root[next node]をroot[start]値に入れます.
DFS(next node)を実行します.
1秒、256 MBメモリ
input :
各ノードの隣接ノードを整理する.
```python
graph = [0]
data = list(map(int, sys.stdin.readline().split()))
for item in data:
graph.append(item)
```
図[0]には、隣接ノードが1から始まり、1から始まるように0が追加されている.
どうやって彼らを組み合わせますか?
ルートノード方式を使用します.
root[now]=root[next node]の場合、ループです.
root = [i for i in range(n + 1)]
def DFS(start):
global cnt
visit[start] = True
next_node = graph[start]
if root[start] == root[next_node]:
cnt += 1
else:
root[next_node] = root[start]
DFS(next_node)隣接ノードを解決するのは自分の場合です.
DFSの挙動は.
visit[start]から処理を開始し、
ルートがnext nodeと異なる場合
root[next node]をroot[start]値に入れます.
DFS(next node)を実行します.
import sys
sys.setrecursionlimit(10000)
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
graph = [0]
data = list(map(int, sys.stdin.readline().split()))
for item in data:
graph.append(item)
root = [i for i in range(n + 1)]
visit = [False] * (n + 1)
cnt = 0
def DFS(start):
global cnt
visit[start] = True
next_node = graph[start]
if root[start] == root[next_node]:
cnt += 1
else:
root[next_node] = root[start]
DFS(next_node)
for i in range(1, n + 1):
if not visit[i]:
DFS(i)
print(cnt)
Reference
この問題について(BOJ 10451シーケンス周期), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/BOJ-10451-순열-사이클テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol