ABC054: C - One-stroke Path

問題

問題文

https://beta.atcoder.jp/contests/abc054/tasks/abc054_c

問題概要

頂点数: N , 辺の数: M の重みなし無向グラフが与えられる.

ただし, このグラフは自己ループや二重辺を持たない.

頂点 1 を始点として, 全ての頂点を1度だけ通る経路は何通りあるか.

解答例

指針

• 全探索

解説

AtCoder Beginner Contest 054のC問題.

N が 8 以下と小さいため全探索をすれば通る.

DFS による解法

頂点 1 を始点として DFS (Depth First Search) を行うことでこの問題を解くことができる.

• C++ による実装例

#include <iostream>
#include <vector>

using namespace std;

// C/C++ の Global 変数は int は 0, bool は false で初期化される
int ans;
bool visited[8];
bool all_visited;

// 隣接リストによるグラフの表現
vector<int> G[8];

// cur: 現在 (current) いる頂点, n: 頂点数
void dfs(int cur, int n) {
    visited[cur] = true;
    all_visited = true;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            all_visited = false;
            break;
        }
    }
    if (all_visited) { ans++; }
    // 範囲 for 文
    for (auto e: G[cur]) {
        if (!visited[e]) {
            dfs(e, n);
            visited[e] = false;
        }
    }
}

int main() {
    // n: 頂点数, m: 辺の数
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        // 0-based index にしたいのでデクリメント
        s--; t--;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    dfs(0, n);

    cout << ans << endl;

    return 0;
}

• Python3 による実装例

#!/usr/bin/python3

import sys

sys.setrecursionlimit(10000)

ans = 0

def dfs(cur, visited, G):
    visited[cur] = True

    if all(visited):
        global ans
        ans += 1

    for c in G[cur]:
        if not visited[c]:
            dfs(c, visited, G)
            visited[c] = False
    return


def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n) ]

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        G[a] += [b]
        G[b] += [a]

    v = [ False for _ in range(n) ]

    dfs(0, v, G)
    print(ans)

main()

標準ライブラリ機能による全探索

{2, 3 ... N} の順列を列挙しその経路が存在するか判定する.

• C++

C++ には next_permutation という非常に便利なものがある.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m, ans = 0;

    vector<int> G[8];
    vector<int> a;

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    for (int i = 1; i < n; i++) {
        a.push_back(i);
    }

    do {
        bool ok = true;
        for (int i = 0; i < n-1; i++) {
            bool tmp = false;
            if (!i) {
                for (auto e: G[0]) {
                    if (e == a[i]) { tmp = true; }
                }
            } else {
                for (auto e: G[a[i-1]]) {
                    if (e == a[i]) { tmp = true; }
                }
            }
            if (!tmp) { ok = false; }
        }
        if (ok) { ans++; }
    } while (next_permutation(a.begin(), a.end()));

    cout << ans << endl;

    return 0;
}

• Python3

Python には itertools というもっと便利なものがある.

#!/usr/bin/python3

from itertools import permutations

def main():
    ans = 0
    n, m = map(int, input().split())
    G = [[] for _ in range(n) ]

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        G[a] += [b]
        G[b] += [a]

    a = list(permutations(range(1, n)))

    for i in a:
        ok = True
        for j in range(len(i)):
            tmp = False
            if j == 0:
                for e in G[0]:
                    if e == i[j]:
                        tmp = True
            else:
                for e in G[i[j-1]]:
                    if e == i[j]:
                        tmp = True
            if not tmp:
                ok = False
        if ok:
            ans += 1

    print(ans)

main()

参考文献

• https://atcoder.jp/img/abc054/editorial.pdf