Problem:


Score : 300 points

Problem Statement

You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.

Here, a self-loop is an edge where a_i = b_i (1≤i≤M), and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).

How many different paths start from vertex 1 and visit all the vertices exactly once?

Here, the endpoints of a path are considered visited.  

For example, let us assume that the following undirected graph shown in Figure 1 is given.

Figure 1: an example of an undirected graph

The following path shown in Figure 2 satisfies the condition.

Figure 2: an example of a path that satisfies the condition

However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.

Figure 3: an example of a path that does not satisfy the condition

Neither the following path shown in Figure 4, because it does not start from vertex 1.

Figure 4: another example of a path that does not satisfy the condition

Constraints

2≦N≦8 

0≦M≦N(N-1)/2 

1≦a_i<b_i≦N 

The given graph contains neither self-loops nor double edges.

Input

The input is given from Standard Input in the following format:

N M  
a_1 b_1  
a_2 b_2
:  
a_M b_M  

Output

Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

The given graph is shown in the following figure:

The following two paths satisfy the condition:

Sample Input 2

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

Sample Output 2

1

This test case is the same as the one described in the problem statement.



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# 基本課題 3．経路探索の解を求める
#
# 5 つの地点 0 ～ 4 を結ぶ道路網が図のようにある ( 図は授業支援システム参照 )
# 始点を 0 とし終点を 4 とした時、0 から 4 に至る経路をすべて求めなさい。
# ただし、同じ地点を２度通ってはいけない
#
# -*- coding: utf-8 -*-

ANS2=[] #0から4までの経路列挙(2次元配列)

#引数
#G:道路網を表す2次元配列(隣接リスト)
#LT:今のところの経路(だんだん広げていく)(最初は[[0]])
#返り値
#広げられなくなるまで広げた経路
#副作用
#ANS2を更新
#ANS2:0から4までの経路
def loot(G,LT):
    if LT==[]:
        return []
    else:    
        ANS=[] #今の地点から一回広げた時点での経路
        for i in range(len(LT)):
            for j in range(len(G[LT[i][-1]])):
                if not(G[LT[i][-1]][j] in LT[i]):
                    TMP=LT[i]
                    ANS.append(TMP+[G[LT[i][-1]][j]])
                else:
                    if not LT[i] in ANS2:
                        ANS2.append(LT[i])         
        return loot(G,ANS)

#2次元リストを標準出力
def print_list(lst):
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            print(ANS2[i][j],end=' ')
        print('')    

N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
               

loot(G,[[0]])

cnt=0

for i in ANS2:
    if len(i)==N:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split()))

P=[]
for m in range(M):
    P.append(list(map(int,input().split())))

from itertools import combinations

ans=0
for c in combinations(range(M),N-1):
    visit = [1]
    P_visit=[]
    v=0
    start=visit[0]
    while v < 100:
        v+=1
        for c_ in c:
            if c_ in P_visit:
                continue
            if P[c_][0] == start:
                visit.append(P[c_][1])
                start = P[c_][1]
                P_visit.append(c_)
                
            elif P[c_][1] == start:
                visit.append(P[c_][0])
                start = P[c_][0]
                P_visit.append(c_)
    
    if len(set(visit))== N:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, m = list(map(int, input().split()))
v = []
for i in range(m):
  tpl = tuple(map(int, input().split()))
  v.append(tpl)
  v.append((tpl[1], tpl[0]))

perms = list(itertools.permutations(v, n-1))
c = 0
for i in perms:
  if i[0][0] != 1:
    continue
  visited = []
  for j in range(len(i)-1):
    if i[j][1] != i[j+1][0]:
      break
    visited.append(i[j][0])
    if i[j+1][1] in visited:
      break
  else:
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p,n):
    q=deque()
    q.append((v,p,1,0))
    log=[0]*n
    log[v-1]=1
    ans=0
    while q:
        V,P,cnt,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            q.append((V,P,cnt,1))
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]:continue
                log[V-1]=1
                q.append((new_v,V,cnt+1,0))
                if cnt==n-1:ans+=1
        else:
            log[P-1]=0
    return ans

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
G=Graph(ab)
#print(G)
ans=dfs(G,1,-1,n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p,n):
    q=deque()
    q.append((v,p,1,0))
    log=[0]*n
    log[v-1]=1
    ans=0
    while q:
        V,P,cnt,S=q.pop()
        if S==0:
            #下に遷移していくときの処理
            q.append((V,P,cnt,1))
            for new_v in G[V-1]:
                if new_v==P:continue
                if log[new_v-1]:continue
                log[V-1]=1
                q.append((new_v,V,cnt+1,0))
                if cnt==n-1:ans+=1
        else:
            log[P-1]=0
    return ans

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
G=Graph(ab)
#print(G)
ans=dfs(G,1,-1,n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
import copy
a=[0]*M
b=[0]*M
for i in range(M):
    a[i],b[i]=map(int,input().split())
D=[[1]]
def route(D):
    E=[]
    D1=copy.deepcopy(D)
    for j in range(len(D)):
        x=D[j][-1]
        for i in range(M):

            if a[i]==x:
                if not b[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(b[i])
                    E.append(D[j])
            elif b[i]==x:
                if not a[i] in D1[j]:
                    D=copy.deepcopy(D1)
                    D[j].append(a[i])
                    E.append(D[j])
    return E
for i in range(N-1):
    D=copy.deepcopy(route(D))
print(len(D))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np
N,M=map(int,list(input().split(" ")))
E_list=[]
for i in range(M):
    p,q=map(int,list(input().split(" ")))
    E_list.append([[p,q]])
def comb(E,m):
    n=len(E)
    if m==0:
        return [[]]
    elif n==m:
        sum=[]
        for i in range(n):
            sum+=E[i]
        return [sum]
    elif n<m:
        return [[]]
    else:
        lis1=E[:-1]
        sum=comb(lis1,m)
        lis2=comb(lis1,m-1)
        k=len(lis2)
        for i in range(k):
            sum.append(lis2[i]+E[-1])
        return sum

def WDS(maps,N):
    d=[np.inf for i in range(N+1)]
    d[1]=0
    queue=[1]
    while queue!=[]:
        v=queue[0]
        queue=queue[1:]
        for w in maps[v]:
            if d[w]==np.inf:
                d[w]=d[v]+1
                queue.append(w)
    return d[1:]
K=comb(E_list,N-1)
k=len(K)
s=0
for i in range(k):
    k_list=K[i]
    m=len(k_list)
    E=defaultdict(lambda:[])
    for j in range(m):
        E[k_list[j][0]].append(k_list[j][1])
        E[k_list[j][1]].append(k_list[j][0])
    g=WDS(E,N)
    if max(g)==N-1:
        s+=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

P = N-1
count = 0
for path in itertools.permutations(ab, P):
  flag = True
  prev = 1
  memo = [0]*N
  for i in range(P):
    memo[prev-1] += 1
    if flag == True:
      if path[i][0] == prev:
        prev = path[i][1]
      elif path[i][1] == prev:
        prev = path[i][0]
      else:
        flag = False
        continue
      if 0 < memo[prev-1]:
        flag = False
        continue
      if i == P-1:
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]
combinations = list(itertools.combinations(AB,N-1))

def check(edges):
    edges_2 = [[] for i in range(N)]
    for e1,e2 in edges:
        edges_2[e1-1].append(e2-1)
        edges_2[e2-1].append(e1-1)
    edges = edges_2
    visited = [False for i in range(N)]
    visited[0] = True
    Q = [(-1,0)]
    while Q:
        a,b = Q.pop()
        c = 0
        for e in edges[b]:
            if e == a:
                continue
            if visited[e]:
                continue
            c += 1
            if c > 1:
                break
            Q.append((b,e))
            visited[e] = True
    if False in visited:
        return False
    return True
ans = 0
for edges in combinations:
    if check(edges):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
checked_list = []       # すでに通ったことのあるリスト
throwgh_point_list = [-1 for i in range(N)]     # 経路のリスト（全探索用）

def dfs(i, current, throwgh_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        global checked_list
        # すでに考慮したことのあるリストの場合
        if throwgh_point_list in checked_list:
            return

        checked_list.append(copy.copy(throwgh_point_list))

        # 全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list)

dfs(0, 0, throwgh_point_list)
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
ans_point_list = []
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        global ans_point_list
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list)

dfs(0, 0, throwgh_point_list)
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = input().split()
    a = int(a)
    b = int(b)
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
V = []
for i in range(M):
    a, b = map(int, input().split())
    V.append((a-1, b-1))


def bfs(G):
    visited = [False] * N
    visited[0] = True
    que = deque([(0, -1, 0)])
    r = 0
    while que:
        ci, p, d = que.popleft()
        for ni in G[ci]:
            if visited[ni] is False:
                visited[ni] = True
                que.append((ni, ci, d+1))
                r = max(r, d+1)

    return r


ans = 0
for i in range(2 ** M):
    if bin(i).count('1') != N-1:
        continue
    else:
        G = {k: [] for k in range(N)}
        for j in range(M):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                (a, b) = V[j]
                G[a].append(b)
                G[b].append(a)
        if bfs(G) == N-1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
V = []
for i in range(M):
    a, b = map(int, input().split())
    V.append((a, b))


def bfs(G):
    if len(G[1]) >= 2:
        return 0
    visited = [False]*N
    visited[0] = True
    que = deque([(1, -1)])
    while que:
        ci, p = que.popleft()
        if len(G[ci]) >= 3:
            return 0
        for ni in G[ci]:
            if ni != p:
                if visited[ni-1]:
                    return 0
                visited[ni-1] = True
                que.append((ni, ci))
    if all(visited):
        return 1
    else:
        return 0


ans = 0
for i in range(2 ** M):
    if bin(i).count('1') != N-1:
        continue
    else:
        G = {k: [] for k in range(N+1)}
        for j in range((2**M).bit_length()):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                (a, b) = V[j]
                # 無向グラフ
                G[a].append(b)
                G[b].append(a)
        ans += bfs(G)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

res = 0
if M < N - 1:
    print(res)
else:
    for course in itertools.combinations(edges, N - 1):

        num_of_v = [0] * N
        for edge in course:
            num_of_v[edge[0]] += 1
            num_of_v[edge[1]] += 1
        if num_of_v[0] != 1 and max(num_of_v) != 2:
            continue

        for root in itertools.permutations(course):
            vertex = [False] + [True] * (N - 1)
            v = 0
            for edge in root:
                if v in edge:
                    nv = edge[0] if v == edge[1] else edge[1]
                    if vertex[nv]:
                        vertex[nv] = False
                        v = nv
                        continue
                break
            else:
                res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

res = 0
if M < N - 1:
    print(res)
else:
    for course in itertools.permutations(edges, N - 1):

        if 0 not in course[0]:
            continue

        num_of_v = [0] * N
        for edge in course:
            num_of_v[edge[0]] += 1
            num_of_v[edge[1]] += 1
        if num_of_v[0] != 1 and max(num_of_v) != 2:
            continue

        vertex = [False] + [True] * (N - 1)
        v = 0
        for edge in course:
            if v in edge:
                nv = edge[0] if v == edge[1] else edge[1]
                if vertex[nv]:
                    vertex[nv] = False
                    v = nv
                    continue
            break
        else:
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, M = map(int, input().split())
edges = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

res = 0
if M < N - 1:
    print(res)
else:
    for path in itertools.permutations(edges, N - 1):
        vertex = [True] * N
        v = 0
        vertex[v] = False
        for edge in path:
            if v in edge:
                nv = edge[0] if v == edge[1] else edge[1]
                if vertex[nv]:
                    vertex[nv] = False
                    v = nv
                    continue
            break
        else:
            res += 1
    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def search(graph, n):
  result = [[] for _ in range(n)]
  if(1 in graph):
    result[0] = [1]
    for nxt in graph[1]:
      if(nxt in graph):
        result[1].append([1, nxt])
        if(2 == n):
          continue
        for nxt2 in graph[nxt]:
          if(nxt2 in graph):
            result[2].append([1, nxt, nxt2])
            if(3 == n):
              continue
            for nxt3 in graph[nxt2]:
              if(nxt3 in graph):
                result[3].append([1, nxt, nxt2, nxt3])
                if(4 == n):
                  continue
                for nxt4 in graph[nxt3]:
                  if(nxt4 in graph):
                    result[4].append([1, nxt, nxt2, nxt3,nxt4])
                    if(5 == n):
                      continue
                    for nxt5 in graph[nxt4]:
                      if(nxt5 in graph):
                        result[5].append([1, nxt, nxt2, nxt3,nxt4,nxt5])
                        if(6 == n):
                          continue
                        for nxt6 in graph[nxt5]:
                          if(nxt6 in graph):
                            result[6].append([1, nxt, nxt2, nxt3,nxt4,nxt5,nxt6])
                            if(7 == n):
                              continue
                            for nxt7 in graph[nxt6]:
                              if(nxt7 in graph):
                                result[7].append([1, nxt, nxt2, nxt3,nxt4,nxt5,nxt6,nxt7])
  return result

n, m = list(map(int, input().split()))
route = [False for _ in range(n)]
gh = {}
for i in range(m):
  start,end = list(map(int, input().split()))
  if(start in gh):
    gh[start].add(end)
  else:
    gh[start] = {end}
  if(end in gh):
    gh[end].add(start)
  else:
    gh[end] = {start}
    
ans = search(gh,n) 
cnt = 0
for arr in ans[n-1]:
  if(set(arr) == {i for i in range(1, n+1)}):
    cnt +=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m=map(int, input().split())
ab=[set(map(int, input().split())) for _ in range(m)]
root=list(itertools.permutations(ab, n-1))
cnt=0
for r in root:
    trace=[i+1 for i in range(n)]
    other=1
    for i in range(0, n-1):
        if other in r[i]:
            try:
                trace.remove(other)
            except ValueError:
                break
            other=list(r[i]-{other})[0]
            continue
        else: break
    try:
        trace.remove(other)
    except ValueError:
        pass
    if trace==[]:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import logging

logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
h = logging.FileHandler("logtest.log")
logger.addHandler(h)


N, M = map(int, input().split())
open_list = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    open_list[a].append(b)
    open_list[b].append(a)

logger.info("open_list: {}\n".format(open_list))

# 探索済みリスト
closed_list = [False] * N
closed_list[0] = True
cnt = 0
level = 1

# 深さ優先探索
def dfs(target):
    global cnt, level
    logger.info("***********open_list[target]: {}".format(open_list[target]))
    if all(closed_list):
        cnt += 1
        logger.info("[level: {}] closed_list: {}".format(level, closed_list))
        logger.info("cnt: {}".format(cnt))
        logger.info("*****************************************")
        return
    # open_listリストのnode
    for node in open_list[target]:
        logger.info("node: {}".format(node))
        logger.info("[level: {}] closed_list: {}".format(level, closed_list))
        # 探索済みでない場合
        if closed_list[node] is False:
            # 探索開始
            closed_list[node] = True
            # 再帰
            level += 1
            dfs(node)
            level = 1
            # levalを戻す
            closed_list[node] = False
            logger.info("[level: {}] closed_list: {}".format(level, closed_list))
    return


dfs(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#C問題
import sys
sys.setrecursionlimit(500000)
N,M = map(int,input().split())
ab=[list(map(int,input().split())) for i in range(M)]
reach=[-1]*(N)
reach[0]=0
ans=0
def cdfs(n):
    global ans
    global reach
    if sum(reach)==0:
        ans+=1
        reach=[-1]*(N)
        reach[0]=0
        return
    else:
        for j in range(N):
            if reach[j] == -1 and ([n+1,j+1] in ab or [j+1,n+1] in ab):
                reach[j] = 0
                cdfs(j)
                reach[j] = -1
            else:
                pass
        return
reach[0]=0
cdfs(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(M)]
for i in range(M):
  E[i] = [int(x) - 1 for x in input().split()]
cnt = 0
for p in range(1, 2 ** M):
  V = [[] for i in range(N)]
  idx = 0
  while p:
    if p % 2:
      V[E[idx][0]].append(E[idx][1])
      V[E[idx][1]].append(E[idx][0])
    idx += 1
    p //= 2
  if sum([len(v) for v in V]) == 2 * (N - 1) and len(V[0]) == 1:
    P = [0] + V[0]
    while len(V[P[-1]]) == 2:
      P += [V[P[-1]][0] if V[P[-1]][0] != P[-2] else V[P[-1]][1]]
    cnt += 1 if len(P) == N else 0
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    A.append(B[i])
    B.append(A[i])

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(2*M):
                if A[i] == start:
                    path(B[i], visited)
            visited.pop()

path(1, [])
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
B = []

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    A.append(B[i])
    B.append(A[i])

result = []
stack = []

def path(start, visited):

    if len(visited) == N:
        if visited not in result:
            result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(2*M):
                if A[i] == start:
                    path(B[i], visited)
            visited.pop()

path(1, [])
print(len(result))