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:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
count=0
for i in range(m):
    data=[[] for i in range(n+1)]
    for j in range(m):
        if j==i:
            continue
        else:
            a,b=ab[j]
            data[a].append(b)
            data[b].append(a)
    flag=[0]*(n+1)
    flag[1]=1
    que=[1]
    cnt=1
    while que:
        h=que.pop()
        for u in data[h]:
            if flag[u]==0:
                flag[u]=1
                que.append(u)
                cnt+=1
    if cnt!=n:
        count+=1
print(count)

Submission status: Accepted

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

ren=[[] for _ in range(N)]
for a,b in AB:
  ren[a-1].append(b)
  ren[b-1].append(a)

def dfs(p):
  seen.append(p)
  for i in ren[p-1]:
    if i not in seen:
      dfs(i)

ans=0
for a,b in AB:
  seen=[]
  ren[a-1].remove(b)
  ren[b-1].remove(a)
  dfs(a)
  ren[a-1].append(b)
  ren[b-1].append(a)
  if len(seen)<N:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


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

    ans = 0
    # i 番目の辺を取り除いても、全ての頂点が連結しているか？
    # Union-Find で連結グラフか判定する
    for i in range(M):
        uf = UnionFind(N) # 最初、全ての頂点が非連結の状態
        for j in range(M):
            if i == j:
                pass # i 番目の辺を無視する
            else:
                # 要素が同じ集合にある＝頂点が連結している
                uf.union(E[j][0], E[j][1])
        # グラフ全体が連結なら、任意の頂点を含む集合のサイズが N のはず
        if uf.size(0) != N:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
l=[]
for i in range(m):
  bridge=list(map(int,input().split()))
  l.append(bridge)
road=[[] for i in range(n)]
for i in range(m):
  road[l[i][0]-1].append(l[i][1])
  road[l[i][1]-1].append(l[i][0])                            
count=0
for i in range(m):
  b=l[i]
  d=[False for j in range(n)]
  d[0]=True
  q=deque([1])
  while q:
    a=q.popleft()
    for j in road[a-1]:
      if (a==b[0] and j==b[1]) or (a==b[1] and j==b[0]):
        pass
      else:
        if d[j-1]==False:
          q.append(j)
          d[j-1]=True
  boolian=True
  for i in d:
    if i==False:
      boolian=False
  if boolian:
    pass
  else:
    count+=1
print(count)

Submission status: Accepted

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

def dfs(x):
  if visit[x]==True:
    return
  visit[x]=True
  for i in range(n):
    if graph[x][i]==True:
      dfs(i)

ans=0
for i in range(m):
  graph=[[False]*n for _ in range(n)]
  for j in range(m):
    if j!=i:
      a,b=AB[j]
      graph[a-1][b-1]=True
      graph[b-1][a-1]=True
  visit=[False]*n
  dfs(0)
  if sum(visit)!=n:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def members(self,x):
    root=self.find(x)
    return [i for i in range(self.n) if self.find(i)==root]
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}
  def __str__(self):
    return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
  
n,m=map(int,input().split())
a,b=[0]*m,[0]*m
for i in range(m):
  a[i],b[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
res=0
for i in range(m):
  UF=UnionFind(n)
  for j in range(m):
    if j!=i:
      UF.union(a[j],b[j])
  if UF.group_count()==2:
    res+=1
print(res)

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
AB =[[int(x) for x in input().split()]for _ in range(M)]
cnt = 0
for j in range(M):
  E = {i:[] for i in range(N)}
  for i in range(M):
    if j==i:
      continue
    a,b= AB[i]
    E[a-1].append(b-1)
    E[b-1].append(a-1)
  visited=[0]*N
  stk=[(0,-1)]
  while stk:
    v,p=stk.pop()
    if visited[v]==1:
      continue
    visited[v]=1
    for i in E[v]:
      if i!=p:
      	stk.append((i,v))
  if 0 in visited:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
graph = []
vis = []
N = 0
M = 0

def dfs(n):
    if vis[n] == True:
        return
    vis[n] = 1
    for i in range(N):
        if graph[n][i] == True:
            dfs(i)

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

ans = 0
for i in range(M):

    graph = []
    for _ in range(N):
        graph.append([False]*N)
    for j in range(M):
        if j != i:
            [a,b] = Data[j]
            graph[a-1][b-1] = True
            graph[b-1][a-1] = True

    vis = [0]*N
    dfs(0)
    if sum(vis) != N:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heapify,heappop,heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    #根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

n,m = inpl()
ab = [0] * m
for i in range(m):
    a,b = inpl()
    ab[i] = (a-1,b-1)

res = 0
for _ in range(m):
    uf = UnionFind(n)
    for i in range(m):
        if _ == i:
            continue
        uf.union(ab[i][0],ab[i][1])
    if uf.size(0) != n:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    answer = 0
    for i in range(M): ## iの辺を消す
        matrix = [[0]*(N) for _ in range(N)]
        for j in range(M):
            if j == i:
                continue
            aa = a[j]-1
            bb = b[j]-1
            matrix[aa][bb] = 1
           
        dist_matrix = floyd_warshall(csgraph=csr_matrix(matrix), directed=False)
        
        if dist_matrix[a[i]-1][b[i]-1] == float('inf'):
            answer += 1
            
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j : [] for j in range(n)}
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

result_ls = [[] for i in range(n)]
def dfs(pos, cnt, last):
    if len(result_ls[pos]) != 0:
        return result_ls[pos][1]
    res = cnt
    result_ls[pos] = [cnt, res]
    for candidate in graph[pos]:
        if candidate == last:
            continue
        _ = dfs(candidate, cnt + 1, pos)
        if _ < res:
            res = _
    result_ls[pos] = [cnt, res]
    return res

dfs(0, 0, -1)
cnt = 0
for res in result_ls:
    if res[0] > res[1]:
        cnt += 1
print(n - 1 - cnt)

Submission status: Accepted

Solution code:
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    chains = list(map(string_to_int, inputs))
    nodes_chain = {i+1: set() for i in range(N)}

    for c in chains:
        [a, b] = c
        nodes_chain[a].add(b)
        nodes_chain[b].add(a)

    modified = True
    count = 0
    while modified:
        modified = False
        for node1 in nodes_chain.keys():
            target_nodes = nodes_chain[node1]
            if len(target_nodes) == 1:
                node2 = target_nodes.pop()
                nodes_chain[node2].remove(node1)
                count += 1
                modified = True
    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
def main():
    n,m=map(int,input().split(' '))
    graph=[[0 for i in range(n)] for j in range(n)]
    graph_del=[]
    ans = 0

    for i in range(m):
        e_1,e_2=map(int,input().split(' '))
        graph[e_1-1][e_2-1]=1
        graph[e_2-1][e_1-1]=1
        graph_del.append((e_1,e_2))

    for i,j in graph_del:
        graph[i-1][j-1]=0
        graph[j-1][i-1]=0
        if connected_components(np.array(graph),return_labels=False)!=1:
            ans += 1
        graph[i-1][j-1]=1
        graph[j-1][i-1]=1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
N, M = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(M)]

graph = [[0] * (N + 1) for _ in range(N + 1)]
for a, b in edge:
  graph[a][b] = 1

answer = 0
INF = 10 ** 9
for a, b in edge:
  # a-bのedgeを取り除いた場合にa-bの距離を測る
  graph[a][b] = INF
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] >= INF:
    answer += 1
  # a-bのedgeを戻す
  graph[a][b] = 1

print(answer)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
edge=[]
from collections import deque
from collections import defaultdict
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    a-=1 
    b-=1 
    edge.append([a,b])
    d[a].append(b)
    d[b].append(a)
def check(d):
    q=deque()
    vis=[0]*n  
    q.append(0)
    vis[0]=1 
    while q:
        t=q.popleft()
        for i in d[t]:
            if not vis[i]:
                vis[i]=1 
                q.append(i)
    return sum(vis)==n 
cnt=0 
for a,b in edge:
    d[a].remove(b)
    d[b].remove(a)
    if not check(d): 
        cnt+=1 
    d[a].append(b)
    d[b].append(a)
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[0] * n for _ in range(n)]  #隣接行列
edge = []
for i in range(m):
	a, b = map(int, input().split())
	graph[a-1][b-1] = 1
	graph[b-1][a-1] = 1
	edge.append([a-1,b-1])

def dfs(x):
	if(vis[x] == 1):
		return
	vis[x] = 1
	for i in range(n):
		if(graph[x][i] == 1):
			dfs(i)


ans = 0
for i in range(m):
	graph[edge[i][0]][edge[i][1]] = 0
	graph[edge[i][1]][edge[i][0]] = 0
	vis = [0] * 60
	dfs(0)
	for j in range(n):
		if(vis[j] == 0):
			ans += 1
			break
	graph[edge[i][0]][edge[i][1]] = 1
	graph[edge[i][1]][edge[i][0]] = 1
print (ans)

Submission status: Accepted

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

N, M = map(int, input().split())
a, b = [], []
graph = [[False] * N for _ in range(N)]
for i in range(M):
    _a, _b = map(int, input().split())
    a.append(_a - 1), b.append(_b - 1)
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = True

ans = 0

for i in range(M):
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = False
    visited = [False] * N
    dfs(0, N, graph, visited)
    bridge = False
    for j in range(N):
        if visited[j] == False:
            bridge = True
    if bridge:
        ans += 1
    graph[a[i]][b[i]] = graph[b[i]][a[i]] = True

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
    

n , m = map(int,input().split())

a = [0] * m
b = [0] * m

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

res = 0
for i in range(m):
    UF = UnionFind(n)
    for j in range(m):
        if j != i:
            UF.union(a[j],b[j])
    if UF.group_count() ==2:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(m)]
graph = [[False] * n for i in range(n)]

for a, b in l:
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True


def dfs(x):
    visited[x] = True
    for i in range(n):
        if graph[x][i] is False:
            continue
        if visited[i] is True:
            continue
        dfs(i)


ans = 0
for i in range(m):
    graph[l[i][0]-1][l[i][1]-1] = False
    graph[l[i][1]-1][l[i][0]-1] = False
    visited = [0] * n
    dfs(0)
    if sum(visited) != n:
        ans += 1
    graph[l[i][0]-1][l[i][1]-1] = True
    graph[l[i][1]-1][l[i][0]-1] = True
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
ls = []
ans = 0
for i in range(M):
  a, b = map(int, input().split())
  dic[a] += [b]
  dic[b] += [a]
  ls += [(a,b)]

for v in ls:
  a, b = v
  stuck = [a]
  log = [True]*(N+1)
  log[a] = False
  count = 1
  while stuck:
    p = stuck.pop()
    if p==a or p==b:
      for e in dic[p]:
        if e==a or e==b:
          continue
        if log[e]:
          log[e] = False
          stuck += [e]
          count += 1
    else:
      for e in dic[p]:
        if log[e]:
          log[e] = False
          stuck += [e]
          count += 1
  if count != N:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
e=[]
for i in range(m):
    e.append(list(map(int,input().split())))
ans=0
for i in range(m):
    g=[[] for _ in range(n)]
    for j in range(m):
        if i==j:
            continue
        g[e[j][0]-1].append(e[j][1])
        g[e[j][1]-1].append(e[j][0])
    visited=[0]*n
    visited[0]=1
    q=[1]
    while len(q)>0:
        a=q.pop(0)
        visited[a-1]=1
        for k in g[a-1]:
            if visited[k-1]==0:
                q+=[k]
    if sum(visited)!=n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

WHITE = 0
GRAY = 1
BLACK = 2


def dfs(s, n, m):
    color = [WHITE] * n

    stack = [s]
    color[s] = GRAY
    while stack:
        u = stack[-1]
        for v, flg in enumerate(m[u]):
            if flg:
                if color[v] == WHITE:
                    color[v] = GRAY
                    stack.append(v)
                    break
        else:
            stack.pop()
            color[u] = BLACK

    cnt = color.count(BLACK)

    return cnt


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

    g = [[0] * n for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        g[a][b] = 1
        g[b][a] = 1

    ans = 0
    for a, b in ab:
        a -= 1
        b -= 1
        cp = deepcopy(g)
        cp[a][b] = 0
        cp[b][a] = 0

        cnt = dfs(0, n, cp)

        if cnt != n:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

graph = {x:[] for x in range(1, n+1)}
for x, y in ab:
    graph[x].append(y)
    graph[y].append(x)

def dfs(v):
    visited.append(v)
    for v2 in graph[v]:
        if v2 not in visited:
            dfs(v2)

res = 0
for a, b in ab:
    graph[a].remove(b)
    graph[b].remove(a)
    visited = []
    dfs(1)
    if len(visited) != n:
        res += 1
    graph[a].append(b)
    graph[b].append(a)

print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

graph = {x:[] for x in range(1, n+1)}
for x, y in ab:
    graph[x] = graph.get(x, []) + [y]
    graph[y] = graph.get(y, []) + [x]

res = 0
for a, b in ab:
    graph[a].remove(b)
    graph[b].remove(a)
    stack = [1]
    visited = []
    while len(stack) > 0:
        v = stack.pop()
        visited.append(v)
        for next in graph[v]:
            if next in visited:
                continue
            if next in stack:
                continue
            stack.append(next)
    if len(visited) != n:
        res += 1
    graph[a].append(b)
    graph[b].append(a)

print(res)

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
nodes = [[] for _ in range(n)]
edges = []
for _ in range(m):
    a,b = map(lambda x:int(x) -1,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
    edges.append((a,b))
ans = 0
for a,b in edges:
    s = deque()
    gone = [0 for _ in range(n)]
    gone[a] = 1
    s.append(a)
    judge = 1
    while s:
        ai = s.popleft()
        for bi in nodes[ai]:
            if (ai,bi) == (a,b):
                pass
            elif bi ==b:
                judge =0
                break
            else:
                if gone[bi]==0:
                    s.append(bi)
                    gone[bi] =1
    if judge:
        ans +=1
print(ans)

Submission status: Accepted

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

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(pass_a)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
Gd = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    Gd[a].append(b)
    Gd[b].append(a)
cnt = 0
for a in range(1,N+1):
    for b in G[a]:
        Gd[a].remove(b)
        Gd[b].remove(a)
        hist = [0 for _ in range(N+1)]
        stack = deque([1])
        while stack:
            cur = stack.popleft()
            hist[cur]=1
            for x in Gd[cur]:
                if hist[x]==0:
                    stack.append(x)
        if sum(hist)<N:
            cnt += 1
        Gd[a].append(b)
        Gd[b].append(a)
print(cnt//2)

Submission status: Accepted

Solution code:
N,M = tuple(map(int,input().split()))
from collections import defaultdict
graph = defaultdict(list)
edges = []
for i in range(M):
  a,b = tuple(map(int,input().split()))
  graph[a].append(b)
  graph[b].append(a)
  edges += [(a,b)]
  
# pathを運んで，その中で
res = 0

def search_path(from_node,to_node):
  queue = [(from_node,set())]
  while queue:
    now, prevs = queue.pop()
    for next_node in graph[now]:
      if {now,next_node} != {from_node,to_node} :
        if next_node == to_node:
          # print(now,next_node,from_node,to_node,prevs)
          return 0
        if next_node not in prevs|{from_node,to_node}:
          queue.append((next_node, prevs|{now}))
  else:
    return 1

print(sum([search_path(from_node,to_node)	for from_node,to_node in edges]))

Submission status: Accepted

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

a = [0] * M
b = [0] * M

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

count = 0
for k in range(M):
    con = [[] for _ in range(N)]
    for i in range(M):
        if i != k:
            con[a[i]].append(b[i])
            con[b[i]].append(a[i])
    visited = [0] * N
    stack = [[0,0]]
    while stack:
        cur,pre = stack.pop()
        if visited[cur] == 1:
            continue
        visited[cur] = 1
        for x in con[cur]:
            if x != pre:
                stack.append([x,cur])
    #print(visited)
    if 0 in visited:
        count += 1

print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [-1 for i in range(n)]

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # contraction
            return self.par[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

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

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        uf.unite(edges[j][0], edges[j][1])

    is_bridge = False
    for j in range(1, n):
        if not uf.same(j-1, j):
            is_bridge = True
            break

    if is_bridge:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
table = collections.defaultdict(list)
for i in range(M):
    a[i], b[i] = map(int, input().split())
    table[a[i]].append(b[i])
    table[b[i]].append(a[i])
bridge = []
for x in table:
    if len(table[x]) < 2:
        bridge.append(x)
prev = 0
now = len(bridge)
while(prev != now):
    for x in table:
        if x not in bridge:
            lenx = len(table[x])
            for y in table[x]:
                if y in bridge:
                    lenx -= 1
            if lenx < 2:
                bridge.append(x)
    prev = now
    now = len(bridge)
ans = 0
for i in range(M):
    if a[i] in bridge or b[i] in bridge:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M= map(int,input().split())
list=[[False for i in range(N)] for j in range(N)]
for i in range (M):
    a,b=map(int,input().split())
    list[a-1][b-1]=True
    list[b-1][a-1]=True
pre = [N for i in range(N)]
low = [N for i in range(N)]
precount=0
count = 0
flag = [False for i in range(N)]
flag[0]=True

def bridge_search (prev,now):
    global precount
    global count
    global flag
    pre[now] = precount
    low[now] = precount
    precount += 1
    flag[now] = True
    for i in range(0,N):
        if(list[now][i] and i != prev):#親ノードへの探索はしない
            if(not flag[i]):#訪れてないなら
                if bridge_search(now,i):#Trueなら辺now-iは橋
                    count += 1
                if low[i] < low[now] and pre[i] > pre[now]:
                    low[now] = low[i]
            else:#訪れているなら
                if low[i] < low[now]:
                    low[now] = low[i]
    #頂点nowの探索終了
    if low[now] >= pre[now]:
        return True
    else:
        return False
    
        
bridge_search(0,0)
print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
      
N,M = map(int,input().split())
Edge = []
for i in range(M):
  a,b = map(int,input().split())
  Edge.append([a-1,b-1])

ans = 0
for i in range(M):
 graph = UnionFind(N)
 for j in range(M):
   if(i != j): 
    graph.Unite(Edge[j][0],Edge[j][1])
 if(graph.Count(0) != N): ans += 1
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]

ans=0
for i in range(m):
    ll=l[:i]+l[i+1:]

    d=[[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i]=0

    for j in ll:
        d[j[0]-1][j[1]-1]=1
        d[j[1]-1][j[0]-1]=1

    d=floyd_warshall(d)

    if float('inf') in d:
        ans+=1

print(ans)

Submission status: Accepted

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

def dfs(s):
    global flag
    global a
    if not flag[s]:
        flag[s] = True
    for g in a[s]:
        if not flag[g]:
            dfs(g)

res = 0
for i in range(m):
    a = [[] for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        else:
            a[master[j][0]-1].append(master[j][1]-1)
            a[master[j][1]-1].append(master[j][0]-1)
    
    flag = [False for _ in range(n)]

    dfs(master[i][0] -1)

    if not all(flag):
        res += 1

print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
Edge = [list(map(int,input().split())) for i in range(m)]

count = 0

for i in range(m):
    Edge_ = Edge[:i]+Edge[i+1:]

    Graph = [[] for i in range(n)]
    for edge in Edge_:
        Graph[edge[0]-1].append(edge[1]-1)
        Graph[edge[1]-1].append(edge[0]-1)

    visited = [False]*n
    visited[0] = True

    stack = [0]
    while stack:
        node = stack.pop()
        for adj in Graph[node]:
            if visited[adj] == False:
                visited[adj] = True
                stack.append(adj)
                
    if not all(visited):
        count += 1
        
print(count)