[鐘万北]ハイキング

展開
に近づく
ルールに従って状況の数を計算します.
[原句]いつも友達同士の学生だけがペアになれる.
2.一部の学生がペアになっていても、違う方法です.
1.隣接リストとして保存し、完全にナビゲートする
最初に思いついた方法で,友人関係図を隣接リストとして保存した後,深さ優先探索により答えが得られた.
隣接テーブルで資料を保存し,一方向ブラウズを行い,同一ペアの繰返し計算を解消しようとしたが,可能なすべてのペアが完全にブラウズできない場合が発生した.
一方的に資料を保存するのではなく、次のペアを探すために加入したコードなどを修正した結果、隣接リストで資料を保存する意味がなくなりました.
...このときコードを逆さまにして書き直します.
2.リレーショナル・マトリクスとして保存し、完全にナビゲート
友人関係図を無方向性の関係行列として格納し,深さ優先探索を行い,答えを導いた.

残りの半分が見つかった場合、DFSにアクセスする配列が格納されているかどうかのように、グラフィックの方向性にかかわらず、個別のタグは重複を解消することができます.

また,この問題の資料を方向図として保存すると,前述したすべての項目を探索できないという問題が発生し,かえって困難になることが分かった.

したがって、新しいコードは、solved_friendsに他の半分の友人が見つかったことを表示する方法を選択し、繰り返しブラウズを回避する.
コード2-リレーショナルマトリクスとアクセス状況配列を使用してDFSを実現

from sys import stdin

test_case = int(stdin.readline())

def solve(solved_friends):
    global pairs, n

    next_friend = -1
    for i in range(n):
        if solved_friends[i] == False:
            next_friend = i
            break
    
    if next_friend == -1:
        return 1

    res = 0
    for i in range(next_friend, n, 1):
        if (not solved_friends[i]) and pairs[i][next_friend]:
            solved_friends[i] = solved_friends[next_friend] = True
            res += solve(solved_friends)
            solved_friends[i] = solved_friends[next_friend] = False

    return res


while test_case:
    n, m = map(int, stdin.readline().strip().split())
    pairs = [[False for _ in range(n)] for _ in range(n)]

    PAIRS_RAW = tuple(int(i) for i in stdin.readline().strip().split())
    for i in range(0, len(PAIRS_RAW), 2):
        pairs[PAIRS_RAW[i]][PAIRS_RAW[i + 1]] = True
        pairs[PAIRS_RAW[i + 1]][PAIRS_RAW[i]] = True

    print(solve([False for _ in range(n)]))

    test_case -= 1

最終的には本の中の解答に似たコードとなり、時事も似ている.

solve関数内の2番目の繰り返し文では、次のペアリングを探索するために再帰的に呼び出される部分(20〜22行目)が表示される.solved_friendsの各エントリは、呼び出しのためにTrueに保持され、その後、Falseに置き換えられることにより、DFSにおいて簡単なナビゲーションを追加のステップを必要とせずに行うことができる.

solve関数に戻り値が含まれているresを見てみましょう.このように検索結果は,伴がなければ0を返し,伴があれば個数を返し,非常に便利であることを示した.