Problem:


Score : 300 points

Problem Statement

You are given an undirected connected graph with N vertices and M edges that does not contain self-loops and double edges.

The i-th edge (1 \leq i \leq M) connects Vertex a_i and Vertex b_i.  

An edge whose removal disconnects the graph is called a bridge.

Find the number of the edges that are bridges among the M edges.  

Notes

A self-loop is an edge i such that a_i=b_i (1 \leq i \leq M).

Double edges are a pair of edges i,j such that a_i=a_j and b_i=b_j (1 \leq i<j \leq M).

An undirected graph is said to be connected when there exists a path between every pair of vertices.

Constraints

2 \leq N \leq 50

N-1 \leq M \leq min(N(N−1)⁄2,50)

1 \leq a_i<b_i \leq N

The given graph does not contain self-loops and double edges.

The given graph is connected.

Input

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 edges that are bridges among the M edges.

Sample Input 1

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

Sample Output 1

4

The figure below shows the given graph:

The edges shown in red are bridges. There are four of them.

Sample Input 2

3 3
1 2
1 3
2 3

Sample Output 2

0

It is possible that there is no bridge.

Sample Input 3

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

Sample Output 3

5

It is possible that every edge is a bridge.



Sample input:
7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7


Sample output:
4

Submission status: Accepted

Solution code:
import copy
N, M = [int(_) for _ in input().split()]
AB = [[int(_) - 1 for _ in input().split()] for _ in range(M)]

G = [[0] * N for _ in range(N)]
for ab in AB:
    G[ab[0]][ab[1]] = 1
    G[ab[1]][ab[0]] = 1


def dfs(Gn, a, x):
    a[x] = 1
    for i in range(N):
        if Gn[x][i] == 1 and a[i] == 0:
            a[i] = 1
            dfs(Gn, a, i)


count = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if G[i][j] == 1:
            Gn = copy.deepcopy(G)
            Gn[i][j] = 0
            Gn[j][i] = 0
            flag = False
            for k in range(N):
                a = [0] * N
                dfs(Gn, a, k)
                if all(a):
                    flag = True
                    break
            if not flag:
                count += 1
print(count)

Submission status: Accepted

Solution code:
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a) #aからb　bからaへの道を配列で作成
    check = [True]*N #checkは既に通った道をFalseとした
    check[0] = False
    Que = [0] #スタートは0から

    while len(Que) != 0:
        now = Que.pop() #スタート位置をpop
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i) #スタート位置から直接行ける場所をスタート位置に加え、その位置を通過済みに
    if True not in check:
        return 0 #スタート位置が無くなった際に全ての位置を通っていれば（つまり道でなければ）0を出力
    else:
        return 1 #道なら1を出力


ans = 0
n, m = map(int,input().split())
edge = []

for i in range(m):
    edge.append([int(i) - 1 for i in input().split()])
for i in range(m):
    copyedge = edge[:i] + edge[i+1:]
    ans += DFS(n, copyedge)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
count = 0
 
for x in edges:
    l = list(range(n))
    for y in edges:
        if y != x:
            l = [l[y[0]-1] if l[i] == l[y[1]-1] else l[i] for i in range(n)]
    if len(set(l)) != 1:
        count += 1
 
print(count)

Submission status: Accepted

Solution code:
import copy

def DFS(start, G):
    stack = []
    check = []
    check.append(start)
    stack.append(start)
    while stack:
        node = stack.pop()
        for child in G[node]:    
            if child not in check:
                check.append(child)
                stack.append(child)
    return set(check)

N, M = (int(i) for i in input().split())
G = []
S = []
for i in range(N + 1):
    G.append([])

for i in range(M):
    a,b = (int(j) for j in input().split())
    G[a].append(b)
    G[b].append(a)
    S.append( (a,b) )

res = 0
for side in S:
    a, b = side 
    dashG = copy.deepcopy(G)
    dashG[a].remove(b)
    dashG[b].remove(a)
    if DFS(a, dashG) != DFS(b, dashG):
        res += 1

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
edge = [[] for _ in range(n)]
ab = []
for _ in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    ab.append((a,b))

def check(a,b):
    visited = [False for _ in range(n)]
    stack = [0]
    while len(stack)>0:
        e = stack.pop()
        visited[e] = True
        for v in edge[e]:
            if (e==a and v==b) or (e==b and v==a):
                continue
            if not visited[v]:
                stack.append(v)
    return all(visited)

res = 0
for a,b in ab:
    if not check(a,b):
        res += 1
print(res)

Submission status: Accepted

Solution code:
graph = 0
node_visited = 0
num_node = 0

def search_route(current_node):
    global node_visited
    node_visited[current_node] = True
    for next_node in range(num_node):
        if graph[current_node][next_node] == False:
            continue
        if node_visited[next_node] == True:
            continue
        search_route(next_node)
    
def main():
    global graph, node_visited, num_node
    num_node, num_edge = map(int, input().split())
    all_edges = [list(map(int, input().split())) for i in range(num_edge)]
    graph = [[False for j in range(num_node)] for i in range(num_node)]
    for edge_s, edge_g in all_edges:
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = True
        
    num_bridge = 0
    for edge_s, edge_g in all_edges:
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = False
        node_visited = [False for i in range(num_node)]
        search_route(current_node = 0)
        for node in node_visited:
            if node == False:
                num_bridge += 1
                break
        graph[edge_s - 1][edge_g - 1] = graph[edge_g - 1][edge_s - 1] = True
    print(num_bridge)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

tmp = []

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

def DFS(now_V, now_Log, ans):
    
    if sum(now_Log)==N:
        return 1
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
    
    return ans

count = 0
          
for i in range(M):
    
    Log = [0]*N
    Log[0] = 1
    
    V[tmp[i][0]-1].remove(tmp[i][1]-1)
    V[tmp[i][1]-1].remove(tmp[i][0]-1)
    if DFS(0, Log, 0)<1:
        count = count+1
    V[tmp[i][0]-1].append(tmp[i][1]-1)
    V[tmp[i][1]-1].append(tmp[i][0]-1)
    
print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    # 負の値はルートで集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        while self.table[x] >= 0:
            # 根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:  # 根が異なる場合
            if self.table[s1] != self.table[s2]:  # グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                # グラフの長さが同じ場合,どちらを根にしても変わらない
                # その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return


n, m = [int(i) for i in input().split()]
a = [0 for i in range(m)]
b = [0 for i in range(m)]
for i in range(m):
    a[i], b[i] = [int(i) - 1 for i in input().split()]

count = 0
for i in range(m):
    # 辺iが橋であるかを判定
    union = UnionFind(n)
    for j in range(m):
        if j != i:
            union.union(a[j], b[j])
    root = union.find(0)
    for j in range(1, n):
        if union.find(j) != root:
            count += 1
            break
print(count)

Submission status: Accepted

Solution code:
(n, m) = list(map(int, input().split()))
bridge = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

for _ in range(m):
    ab = list(map(int, input().split()))
    bridge[ab[0]][ab[1]] = 1
    bridge[ab[1]][ab[0]] = 1

polygon = []
def search(before, nowi, route):
    global bridge
    for i in range(1, n + 1):
        if before == i or nowi == i :
            continue
        if bridge[nowi][i] == 1:
            if i in route:
                for j in range(len(route)):
                    if route[j] == i:
                        polygon.append(route[j:len(route) + 1])
                        break
                continue
            else:
                search(nowi, i, route + [i])
search(1, 1, [1])

for i in polygon:
    for j in range(1, len(i)):
        bridge[i[j-1]][i[j]] = 0
        bridge[i[j]][i[j-1]] = 0

print(sum(map(sum, bridge)) // 2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[]
d=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    x.append((a-1,b-1))
ans=0
for i in x:
    t=set([i[0]])
    r=set()
    while len(t):
        o=t.pop()
        for j in d[o]:
            if j not in r and len(set([o,j])&set([i[0],i[1]]))!=2:
                r.add(j)
                t.add(j)
    if len(r)!=n: ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(w) for w in input().split()])
s.sort(key=lambda x:(x[0], x[1]))
adj = []
for i in range(n):
    adj.append([])
for i in range(n):
    for j in range(n):
        adj[i].append(0)
#鱗屑行列
for i in range(m):
    adj[s[i][0] - 1][s[i][1] - 1] = 1
    adj[s[i][1] - 1][s[i][0] - 1] = 1

#深さ優先探索
labelli = [-1]*n
label = 0
v = 0
labelli[0] = label
p = 0
back = []
backnumber = []
q = 0
count = 0
for h in range(m):
    if h == 0:
        adj[s[h][0] - 1][s[h][1] - 1] = 0
        adj[s[h][1] - 1][s[h][0] - 1] = 0
    else:
        adj[s[h - 1][0] - 1][s[h - 1][1] - 1] = 1
        adj[s[h - 1][1] - 1][s[h - 1][0] - 1] = 1
        adj[s[h][0] - 1][s[h][1] - 1] = 0
        adj[s[h][1] - 1][s[h][0] - 1] = 0
        q = 0
        labelli = [-1] * n
        label = 0
        labelli[0] = label
    while q == 0:
        for j in range(n):
            if adj[v][j] == 1 and labelli[j] == -1:#未探索部分を掘る
                label += 1
                v = j
                labelli[j] = label
                p = 1
                break
        if v == 0:
            for l in range(n):
                if adj[v][j] == 1 and labelli[j] == -1:#初期地点で、未探索部分があるかチェック、なければ終了
                    break
                if l == n - 1:
                    q = 1
                    p = 1
                    if min(labelli) == -1:
                        count += 1
        if p == 0:#未探索がなければ戻る
            for k in range(n):
                if adj[v][k] == 1:
                    if labelli[v] > labelli[k]:
                        back.append(abs(labelli[v] - labelli[k]))
                        backnumber.append(k)
            v = backnumber[back.index(min(back))]
            back = []
            backnumber = []
        p = 0

print(count)

Submission status: Accepted

Solution code:
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a].append(b)
        matrix[b].append(a)
        
    check = [True]*N
    check[0] = False
    Que = [0]

    while len(Que) != 0:
        now = Que.pop()
        for i in matrix[now]:
            if check[i] == True:
                check[i] = False
                Que.append(i)
    if True not in check:
        return 0
    else:
        return 1
            
        

ans = 0
N, M = map(int, input().split())
edge = []

for i in range(M):
    edge.append([int(i) - 1 for i in input().split()])
    
for i in range(M):
    copyedge = edge[:i] + edge[i+1:] 
    ans += DFS(N, copyedge)
print(ans)

Submission status: Accepted

Solution code:
class Unionfind:
  def __init__(self,n):
     self.Tree=[i for i in range(n)]

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      self.Tree[s1]=s2
      
N,M=map(int,input().split())
Uf=Unionfind(N)
Flag=0
B=0
A=[]
Edge=[[int(i) for i in input().split()] for i in range(M)]
for m in range(M):
  Edge_copy=list(Edge)
  del Edge_copy[m]
  for e in Edge_copy:
    Uf.unite(e[0]-1,e[1]-1)
  for a in range(N):
    A.append(Uf.find(a))
  for n in range(N-1):
    if Uf.find(n)!=Uf.find(n+1):
      Flag=1
      break
  if Flag==1:
    B+=1
  Flag=0
  Uf=Unionfind(N)
  A=[]
print(B)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
List=[[int(i) for i in input().split()] for i in range(M)]
S=0
for i in range(M):
  new_List=list(List)
  del new_List[i]
  islands=[1]
  for i in islands:
    for j in new_List:
      if i in j:
        j=[item for item in j if item not in islands]
        islands.extend(j)
  if len(islands)<N:
    S+=1
print(S)

Submission status: Accepted

Solution code:
def f(v,e):
  for x in v:
    if len(e[x]) == 1:
      y = e[x][0]
      v.remove(x)
      e[x] = []
      e[y].remove(x)
      return f(v,e)+1
  return 0

n,m = map(int,input().split())
v = list(range(1,n+1))
e = [[]]*(n+1)
for _ in [0]*m:
  x,y = map(int,input().split())
  e[x] = e[x] + [y]
  e[y] = e[y] + [x]
print(f(v,e))

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
A=[]
L=[[1000for i in range(N)]for j in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    A.append([a,b])
    L[a-1][b-1]=1
    L[b-1][a-1]=1
    
for j in range(N):
    L[j][j]=0

#print(L)
l=copy.deepcopy(L)

cnt=0
for k in range(M):
    L=copy.deepcopy(l)
    L[A[k][0]-1][A[k][1]-1]=1000
    L[A[k][1]-1][A[k][0]-1]=1000
    for x in range(N):
        for y in range(N):
            for z in range(N):
                if L[y][z]>L[y][x]+L[x][z]:
                    L[y][z]=L[y][x]+L[x][z]
    #print(L[A[k][0]-1][A[k][1]-1])
    if L[A[k][0]-1][A[k][1]-1]>=1000:
        cnt+=1
    L[A[k][0]-1][A[k][1]-1]=1
    L[A[k][1]-1][A[k][0]-1]=1
#print(L)   
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = []
array1 = [[] for _ in range(N+1)]
result = 0

for _ in range(M):
    a, b = map(int, input().split())
    ab.append([a, b])
    array1[a].append(b)
    array1[b].append(a)

for i in ab:
    array2 = [j[:] for j in array1]
    array2[i[0]].remove(i[1])
    array2[i[1]].remove(i[0])
    L = []
    save = []
    x = 1
    
    while True:
        if not x in L:
            L.append(x)
            save.append(x)

        if len(L) == N:
            break

        flag = True
        for j in array2[x]:
            if not j in L:
                x = j
                flag = False
                break

        if flag:
            del save[-1]
            if not save:
                result += 1
                break

            x = save[-1]

print(result)

Submission status: Accepted

Solution code:
def DFS(start,e):
    global edge
    global g
    global visited
    visited[start]=1

    cant=None
    if(e[0]==start):
        cant=e[1]
    elif(e[1]==start):
        cant=e[0]
    for ed in g[start]:
        if(ed==cant):
            continue
        if(visited[ed]==None):
            DFS(ed,e)
            

n,m=map(int,input().split())
g=[[] for _ in range(n)]
edge=[]

for _ in range(m):
    v,w=map(int,input().split())
    g[v-1].append(w-1)
    g[w-1].append(v-1)
    edge.append((v-1,w-1))


ans=0
for e in edge:
    visited=[None]*n
    DFS(0,e)
    flag=True
    for i in range(n):
        if(visited[i]==None):
            flag=False
    if(not flag):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import copy

# Generate Graph as Dict
N, M = list(map(int, input().split()))
G = dict()
paths = []
for i in range(0,M):
    a, b = list(map(int, input().split()))
    paths.append([a,b])
    if a in G:
        G[a] += [b]
    else:
        G[a] = [b]
    if b in G:
        G[b] += [a]
    else:
        G[b] = [a]

# Depth First Search
def dfs(s):
    visited[s-1] = True
    for p in _G[s]:
        if visited[p-1]:
            continue
        else:
            dfs(p)

# Check if the graph is connected for M cases
ans = 0

for i in range(M):
    _G = copy.deepcopy(G)
    _G[paths[i][0]].remove(paths[i][1])
    _G[paths[i][1]].remove(paths[i][0])
    
    visited = [False for i in range(N)]
    dfs(1)
    if not all(visited):
        # Count up if not connected
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
sides = []
def dfs(now):
    history[now] = 1
    for i in List[now]:
        if history[i] == 0:
            dfs(i)
    flag = 0
    for i in range(1, N+1):
        if history[i] == 0:
            flag = 1
    if flag == 0:
        return 0
    else:
        return 1
for i in range(M):
    sides.append(list(map(int, input().split())))

ans = 0
for k in range(M):
    side = sides[:]
    del side[k]
    List = [[] for i in range(N+1)]
    for i in range(M-1):
        List[side[i][0]].append(side[i][1])
        List[side[i][1]].append(side[i][0])

    history = [0 for i in range(N+1)]
    ans += dfs(1)



print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def dfs(v):
    global adjacency_mat, visited
    st = deque([]) # stack
    st.append(v)
    while st:
        # stackから取り出す
        h = st.pop()
        visited[h] = True
        for i in range(N):
            # 辺がないなら何もしない
            if adjacency_mat[h][i] == None:
                continue
            # すでに到達したことがあるなら何もしない
            if visited[i] == True:
                continue
            # stackに加える
            st.append(i)

if __name__ == "__main__":
    N, M = map(int, input().split())
    list_ab = [[] for _ in range(M)]
    adjacency_mat = [[None]* N for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        list_ab[i].append(a-1)
        list_ab[i].append(b-1)
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
        
    ans = 0
    for a, b in list_ab:
        visited = [False] * N
        # ある辺をなくす
        adjacency_mat[a][b] = None
        adjacency_mat[b][a] = None
        # 全ての辺を訪れることができるかどうか探索
        dfs(0)
        # 全ての辺を訪れることができるかどうか
        if sum(visited) < N:
            ans += 1
        # 元に戻す
        adjacency_mat[a][b] = 1
        adjacency_mat[b][a] = 1
    print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    global adjacency_mat, visited
    st = [] # stack
    st.append(v)
    while st:
        # stackから取り出す
        h = st.pop()
        visited[h] = True
        for i in range(N):
            # 辺がないなら何もしない
            if adjacency_mat[h][i] == None:
                continue
            # すでに到達したことがあるなら何もしない
            if visited[i] == True:
                continue
            # stackに加える
            st.append(i)

if __name__ == "__main__":
    N, M = map(int, input().split())
    list_ab = [[] for _ in range(M)]
    adjacency_mat = [[None]* N for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        list_ab[i].append(a-1)
        list_ab[i].append(b-1)
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
        
    ans = 0
    for a, b in list_ab:
        visited = [False] * N
        # ある辺をなくす
        adjacency_mat[a][b] = None
        adjacency_mat[b][a] = None
        # 全ての辺を訪れることができるかどうか探索
        dfs(0)
        # 全ての辺を訪れることができるかどうか
        if sum(visited) < N:
            ans += 1
        # 元に戻す
        adjacency_mat[a][b] = 1
        adjacency_mat[b][a] = 1
    print(ans)

Submission status: Accepted

Solution code:
def search(s, m, n, bridge):
    c = [1]
    d = [1]
    for k in range(n):
        cc = []
        for i, ci in enumerate(c):
            tmp = []
            for j in range(m):
                if j == bridge:
                    continue
                elif s[j][0] == ci and s[j][1] not in d:
                    tmp.append(s[j][1])
                elif s[j][1] == ci and s[j][0] not in d:
                    tmp.append(s[j][0])
            cc += tmp
            d += tmp
        if cc == []:
            break
        else:
            c = cc
    if len(d) == n:
        return 0
    else:
        return 1

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
ans = 0
for i in range(m):
    ans += search(s, m, n, i)
print(ans)

Submission status: Accepted

Solution code:
import queue
from heapq import heappush, heappop

class Graph:

    INF = float('inf')
    
    def __init__(self,v_num,is_directed = False):
        self.is_directed = is_directed
        self.v_num = v_num
        self.E = []
        self.v_s_list = [[] for i in range(self.v_num)]
        
    def appendEdge(self,v1,v2,weight=1):
        if max(v1,v2,self.v_num-1)>=self.v_num or min(v1,v2)<0:
            print("ERROR: The vertex ID is wrong.")
            return False

        self.E.append([v1,v2,weight])
        
        if self.is_directed:
            self.v_s_list[v1].append([v2,weight])
        else:
            self.v_s_list[v1].append([v2,weight])
            self.v_s_list[v2].append([v1,weight])
        
        
    def BFS(self,v,usage="SSSP"):
        is_processed = [False for i in range(self.v_num)]
        distance_list = [Graph.INF for i in range(self.v_num)]
        Q = queue.Queue()
        Q.put(v)
        is_processed[v]=True
        distance_list[v] = 0
        while not Q.empty():
            v1 = Q.get()
            for v2 in self.v_s_list[v1]:
                if not is_processed[v2[0]]:
                    is_processed[v2[0]] = True
                    distance_list[v2[0]] = min(distance_list[v1]+1,distance_list[v2[0]])
                    Q.put(v2[0])
        if usage=="SSSP":
            return distance_list
        elif usage=="ConnectedComponent":
            cc_list = []
            for i in range(self.v_num):
                if is_processed[i]:
                    cc_list.append(i)
            return cc_list

    def getSSSPwithBFS(self,v):
        return self.BFS(v,"SSSP")
        
    def getConnectedComponent(self,v):
        return self.BFS(v,"ConnectedComponent")
        
    def getSSSPwithBellmanFord(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]

        for i in range(self.v_num-1):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if distance_list[v2] > distance_list[v1] + d:
                    distance_list[v2] = distance_list[v1] + d
                    pre_list[v2] = v1
                    
        negative_loop_list = [False for i in range(self.v_num)]
        
        for i in range(self.v_num):
            for e in self.E:
                v1 = e[0]
                v2 = e[1]
                d = e[2]
                if d + distance_list[v1] < distance_list[v2]:
                    distance_list[v2] = d + distance_list[v1]
                    pre_list[v2] = v1
                    negative_loop_list[v2] = True
        
        return distance_list, pre_list, negative_loop_list

    def getSSSPwithDijkstra(self,v):
        distance_list = [Graph.INF for i in range(self.v_num)]
        distance_list[v] = 0
        pre_list = [None for i in range(self.v_num)]
        
        PQ = []
        for i in range(self.v_num):
            heappush(PQ,(distance_list[i],i))
        while len(PQ)>0:
            d,v1 = heappop(PQ)
            for v2 in self.v_s_list[v1]:
                if distance_list[v2[0]] > d + v2[1]:
                    distance_list[v2[0]] = d + v2[1]
                    pre_list[v2[0]] = v1
                    heappush(PQ,(distance_list[v2[0]],v2[0]))
        return distance_list,pre_list
    

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

graph_buf = []
for i in range(M):
    a,b = list(map(int,input().split()))
    graph_buf.append([a,b])
count=0
for i in range(M):
    G = Graph(N)
    for j in range(M):
        if i!=j:
            G.appendEdge(graph_buf[j][0]-1,graph_buf[j][1]-1)
    if len(G.getConnectedComponent(0))!=N:
        count+=1

print(count)

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

def walk(pos, pos_prev, footprint):
    # print("#", pos, footprint)
    footprint = (2 ** pos) | footprint
    ret = footprint
    for pos_next in route[pos]:
        # print("##", pos_next, (2 ** pos_next) & footprint)
        if (2 ** pos_next) & footprint > 0: continue
        ret = ret | walk(pos_next, pos, footprint)
        if ret == (2 ** N - 1): return 2 ** N - 1 # speed test
    return ret

ans = 0
for ai, bi in ab:
    # temporary remove
    route[ai - 1].remove(bi - 1)
    route[bi - 1].remove(ai - 1)
    # connection check
    if walk(0, -1, 0) < (2 ** N - 1): ans += 1
    # recovery
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

print(ans)

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

def walk(pos, pos_prev, footprint):
    # print("#", pos, footprint)
    footprint = (2 ** pos) | footprint
    ret = footprint
    for pos_next in route[pos]:
        # print("##", pos_next, (2 ** pos_next) & footprint)
        if (2 ** pos_next) & footprint > 0: continue
        ret = ret | walk(pos_next, pos, footprint)
    return ret

ans = 0
for ai, bi in ab:
    # temporary remove
    route[ai - 1].remove(bi - 1)
    route[bi - 1].remove(ai - 1)
    # connection check
    if walk(0, -1, 0) < (2 ** N - 1): ans += 1
    # recovery
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)

print(ans)

Submission status: Accepted

Solution code:
def solve(N, M, ABs):
    ans = 0
    for i in range(M):
        adjMat = [[0 for _ in range(N)] for _ in range(N)]
        for k, (a, b) in enumerate(ABs):
            if k != i:
                adjMat[a - 1][b - 1] = 1
                adjMat[b - 1][a - 1] = 1

        def dps(a, visited):
            n = [i for i, b in enumerate(adjMat[a]) if b == 1]
            for nn in n:
                if nn not in visited:
                    visited.append(nn)
                    dps(nn, visited)
            return visited

        visited = dps(0, [])
        if len(visited) != N:
            ans += 1
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

Submission status: Accepted

Solution code:
import copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def can_goal(start, end, line_map, memo):
    if start == end:
        return True
    _can_goal = False
    if start in line_map:
        for next_start in line_map[start]:
            if memo[start][next_start] or memo[next_start][start]:
                continue
            memo[start][next_start] = True
            memo[next_start][start] = True
            _can_goal = can_goal(next_start, end, line_map, memo)
            if _can_goal:
                break
    return _can_goal


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

line_map = {}
memo = {}
for line in lines:
    if line.a in line_map:
        line_map[line.a].append(line.b)
        memo[line.a][line.b] = False
    else:
        line_map[line.a] = [line.b]
        memo[line.a] = {}
        memo[line.a][line.b] = False
    if line.b in line_map:
        line_map[line.b].append(line.a)
        memo[line.b][line.a] = False
    else:
        line_map[line.b] = [line.a]
        memo[line.b] = {}
        memo[line.b][line.a] = False

cnt = 0
for line in lines:
    m = copy.deepcopy(memo)
    start = line.a
    end = line.b
    m[end][start] = True
    m[start][end] = True
    if not(can_goal(start, end, line_map, m)):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def dfs(v):
    visited[v]=True
    for v2 in range(n):
        if graph[v][v2]==False:
            continue
        if visited[v2]==True:
            continue
        dfs(v2)
        
n, m = map(int, input().split())

alis=[]
blis=[]
graph=[[False] * n for i in range(n)]

#隣接行列のセット
for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1]=True
    graph[b-1][a-1]=True
    alis.append(a-1)
    blis.append(b-1)
    
ans=0

for i in range(m):
    #1本辺を落とす
    graph[alis[i]][blis[i]]=False
    graph[blis[i]][alis[i]]=False
    visited=[False]*n
    dfs(0)
    bridge=False
    for j in range(n):
        if visited[j]==False:
            bridge=True
    if bridge:
        ans+=1
    graph[alis[i]][blis[i]]=True
    graph[blis[i]][alis[i]]=True

print(ans)

Submission status: Accepted

Solution code:
import sys

def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    def addSpan(d,a,b):
        if a in d:
            d[a].add(b)
        else:
            d[a]={b}
    dT ={}
    for a,b in aAB:
        addSpan(dT,a,b)
        addSpan(dT,b,a)
    #とりあえずDFSで全検索だ
    iC = 0
    for a,b in aAB:
        iR = 1
        for i in dT[a] - {b}:
            aSt = [i]
            vP = {a}
            while aSt:
                iP = aSt.pop()
                vP.add(iP)
                if iP == b:
                    iR = 0
                    break
                else:
                    for nP in dT[iP] - vP:
                        aSt.append(nP)
            if iR == 0:
                break
        iC += iR
    print(iC)
解()

Submission status: Accepted

Solution code:
def dfs(v, n, graph, visited):
    visited[v] = True
    for v2 in range(n):
        if not graph[v][v2]:
            continue
        if visited[v2]:
            continue
        dfs(v2, n, graph, visited)


n, m = [int(v) for v in input().split()]
graph = [[False] * n for i in range(n)]
a = []
b = []
for i in range(m):
    v1, v2 = [int(v) for v in input().split()]
    v1 -= 1
    v2 -= 1
    a.append(v1)
    b.append(v2)
    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

ans = 0
for i in range(m):
    graph[a[i]][b[i]] = False
    graph[b[i]][a[i]] = False

    visited = [False] * n
    dfs(0, n, graph, visited)
    if False in visited:
        ans += 1

    graph[a[i]][b[i]] = True
    graph[b[i]][a[i]] = True

print(ans)