One-stroke Pathができない話

こんにちは。CPPXのCです。

今年に入ってからAtCoderを始めたのでその備忘録を書きとどめたいと思います。

競技プログラミング初心者なのでABCから挑戦しているのですが、C問題で詰まってしまったので書きとどめておきます。

概要

問題のOne-stroke Pathがこちらです。

C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder

掻い摘んで説明すると、N個の頂点と、その頂点同士をつなぐ辺がM個与えられたとき、すべての頂点を一筆書きで通る道筋は何通りあるか出力せよ、という問題です。

解法

条件を見て見た限りでは、与えられる頂点の数が8個以下とかなり少ないので、全探索で解けるだろうということで全探索で解いてみることにしました。
とりあえず入力を受け取らないと話にならないので、入力を配列として受け取ります。

N, M = map(int, input().split())

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])

与えられるのは無向グラフなので、頂点の位置に自分が進めるノードをすべてつっこみます。

全探索をすること自体はじめてだったので、とりあえず再帰関数を使ってみることにしました。

def travel(now, nextnodes, visited):
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        travel(node - 1, lis[node - 1], visited[:])


travel(0, lis[0], [])
print(len(list(filter(lambda i : len(i) is N, ends))))

自分の位置と自分から進むことのできるノード、すでに訪れたノードがすべてつっこまれている配列を引数にわたし再帰していきます。
一筆書きなので、これで訪れたことのあるノードが与えられた頂点の数と一致している配列の数を取り出せば答えがでるはずです。

結果

入力例を入れてみます。

入力1

3 3
1 2
1 3
2 3

出力1

2

入力2

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

出力2

1

両方通っています。よし、解けた！とおもい提出するとREの文字が。なぜだろう…

もしかして再帰関数がわるいのかな？と思いキューを使って探索してみることに。

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now + 1)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node - 1, lis[node - 1], visited[:]])

print(len(list(filter(lambda i : len(i) is N, ends))))

やっていることは同じなので、入力例は当然通ります。

しかし提出してみると再びREの文字が。

結局原因がわからず、問題はしばらく放置することになってしまいました。 なぜなんだ…

---

追記

2017.5.31. 追記

自己解決したので追記しておきます。

入力を受け取る部分で、前回までは

N, M = map(int, input().split())

l = []

for i in range(N):
    l.append(list(map(int, input().split())))

lis = [[] for i in range(N)]

for i in range(N):
    lis[l[i][0] - 1].append(l[i][1])
    lis[l[i][1] - 1].append(l[i][0])

このように書いていたのですがこれがまずかったようです。
よく読んでみると辺と頂点の数は必ずしも同じではないようです。 頂点Nと辺Mの数が同じだと思い込んでいました…

正しくはこうですね。

N, M = map(int, input().split())

l = []

for i in range(M):
    l.append(list(map(lambda x: int(x) - 1, input().split())))

lis = [[] for i in range(N)]

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

頂点Nの数より辺Mの数のほうが多いことも当然ありうるので、ノードをつっこむときは辺の数で回さないとだめみたいです。ついでにインデックスと頂点の位置がずれていてめんどくさくなっていた部分も直しました。全文は下記のようになっています。

N, M = map(int, input().split())

l = []

for i in range(M):
    l.append(list(map(lambda x: int(x) - 1, input().split())))

lis = [[] for i in range(N)]

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

que = [[0, lis[0], []]]
ends = []

while que:
    now, nextnodes, visited = que.pop()
    ends.append(visited)
    visited.append(now)
    for node in nextnodes:
        if node in visited:
            continue
        que.append([node, lis[node], visited[:]])

print(len(list(filter(lambda ii: len(ii) is N, ends))))