[図]白駿9466-TUM計画

質問アドレス:https://www.acmicpc.net/problem/9466
ブリーフィング

回答時間
[]20分以内に回答を完了
[]40分以内に回答を完了
[]1時間以内にプールを完了する
[]2時間以内にプールを完了する
[]プールの失敗

欠落
[]実装能力
[]問題解決能力
[]背景知識

[問題の説明]
この問題は簡単に言えば,複数の接続された図形を生成する問題である.
問題の条件とする.

第1行試験盤箱数T

第

行生徒数(2<=n<=10000)

3行目は、選択した生徒の番号(1

から2、3回の

を繰り返す.
このようにあげます.
[コード]
第1の方法は、選択された学生の番号リストとアクセスリストを学生の数に基づいてリストし、最初の学生から最後に学生のインデックスで巡回して、その学生が選択した学生の番号が接続された図形を形成しているかどうかを知る方法を想定しているが、どのように実現されるかをよく理解できないため、別の方法を選択している.ramのソースコードを見て分析した.
[ソースコード]
ソースアドレス:https://suri78.tistory.com/128

import sys

#  테스트 케이스 갯수
testcase = int(sys.stdin.readline())

#  테스트 케이스 갯수만큼 데이터 입력받음
for _ in range(testcase):			
    #  n = 총 학생의 수
    n = int(sys.stdin.readline())			
    # 선택된 학생의 리스트 choice와 방문여부를 저장하는 visited 리스트
    choice = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [0] * (n + 1)
	
    # 연결된 그래프의 갯수
    group = 1
    # 총 학생의 수 만큼 순회
    for i in range(1, n + 1):
    	# 만약 i번 학생의 선택지에 방문하지 않았다면(visited[i]가 0이라면)
        if visited[i] == 0:
            # visited[i]가 0일 때까지
            while visited[i] == 0:
            	# i번쨰 학생 방문여부에 group변수의 값을 대입하고 
                visited[i] = group
                # i 를 i번쨰 학생이 선택한 학생의 번호로 바꾼다.
                i = choice[i]
   			#만약 visited[i]가 group 변수와 같다면
            while visited[i] == group:
            	# visited[i]를 -1로 바꿔주고
                visited[i] = -1
                # i를 i번째 학생이 선택한 학생의 번호로 바꾼다.
                i = choice[i]
            #그리고 group 변수의 값에 1을 추가한다.
            group += 1

    # 총 이어진 그래프의 갯수를 담을 count 변수
    count = 0
    #방문 리스트를 모두 돌아
    for v in visited:
    	# 만약 리스트 값이 0보다 크다면 (즉 이어진 그래프가 되었다면)
        if v > 0:
           # count 변수에 1을 추가
            count += 1
   # 카운트 변수 출력
    print(count)

この問題の主な解決方法は接続された図形数を数えることである.上のコードではgroup変数とアクセスリストに、インデックスの2番目の学生が選択した学生と別の学生が選択した学生が表示されます.最後の学生が選択した学生番号が最初の学生番号である場合(簡単に言えば、巡視が完了して最初の始点に戻った場合)、これらの接続は接続のグラフィックを形成するため、同じグループ変数値に代入されます.接続がない場合、これらの接続は接続されたグラフィックを形成しないため、group変数の値に1を追加して、次のグラフィックを検索する際の混乱を低減します.また,接続された図形はすべて0より大きいグループ変数値が代入されているため,代入−1の未接続図形の数字を求めれば,この問題の正解が得られる.