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:
#075-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()
#UnionFindクラス
class UnionFind(object):
 
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
 
    def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
    # xとyの根を結合させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=IL()
nl=[]
for i in range(m):
    f,t=IL()
    nl.append([f-1,t-1])
ans=0
for i in range(m):
    uf=UnionFind(n)
    flag=False
    for j in range(m):
        if i==j:
            continue
        uf.union(nl[j][0],nl[j][1])
    nl.append(t)
    for j in range(n):
        for k in range(n):
            if not uf.same(j,k):
                flag=True
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(graph, node_start, visited):
    if node_start in visited:
        return visited
    visited.append(node_start)
    for node_end in graph[node_start]:
        dfs(graph, node_end, visited)
    return visited

def main():
    N, M = map(int, input().split())

    graph = defaultdict(list)
    edges = []

    # 無向グラフの表現
    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        edges.append((a, b))

    answer = 0
    for a, b in edges:
        # a, b間のエッジの削除
        graph[a].remove(b)
        graph[b].remove(a)

        visited = dfs(graph, 1, [])
        if len(visited)!= N:
            answer += 1

        # エッジの修復
        graph[a].append(b)
        graph[b].append(a)

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def rootT(x, cnt):
  cnt += 1
  if x == T[x]:
    return x, cnt
  x = T[x]
  return rootT(x, cnt)

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

Ans = 0
# それぞれの辺を除いたときに
for i in range(M):
  L = ab[:i] + ab[i + 1:]
  
  # 連結かどうか調べる
  T = [i for i in range(N + 1)]
  for j in L:
    # 根っこを取得
    a = rootT(j[0], 0)
    b = rootT(j[1], 0)
    # 異なっていたら
    if a[0] != b[0]:
      # 短いほうをくっつける
      if a[1] > b[1]:
        T[b[0]] = a[0]
      else:
        T[a[0]] = b[0]

  flag = False
  t = rootT(T[1], 0)[0]
  for j in range(2, N + 1):
    if rootT(T[j], 0)[0] != t:
      flag = True
      break
  if flag:
    Ans += 1

print(Ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

ab = []
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
    
def dfs(x):
    global flag
    flag[x] = True
    for k in range(n):
        if bridge[x][k] == True:
            bridge[x][k] = False
            dfs(k)
            
           
ans = 0
for i in range(m):
    bridge = [[False for i in range(n)] for i in range(n)]
    for j in ab[0:i] + ab[i+1:m]:
        bridge[j[0] - 1][j[1] - 1] = True
        bridge[j[1] - 1][j[0] - 1] = True   
    flag = [False for j in range(n)]
    dfs(0)
    if flag.count(False) > 0:
        ans += 1
        
print(ans)

Submission status: Accepted

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

v = [i for i in range(1,N+1)]
e = [[]]*(N+1)
for i in range(M):
  a, b = map(int,input().split())
  e[a] = e[a] + [b]
  e[b] = e[b] + [a]

def dfs(v, e):
  for num in v:
    if(len(e[num]) == 1):
      tmp_num = e[num][0]
      v.remove(num)
      e[num] = []
      e[tmp_num].remove(num)
      #print(e,v)
      return dfs(v, e)+1
  return 0
print(dfs(v, e))

Submission status: Accepted

Solution code:
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
    
n, m = map(int, input().split())
a, b = [], []
ans = 0
for i in range(m):
    ta, tb = map(int,input().split())
    a.append(ta-1)
    b.append(tb-1)
    
for i in range(m):
    par = []
    rank = []
    diff = set()
    for j in range(n): # 初期化
        par.append(j)
        rank.append(0)
    for j in range(m):
        if j == i:
            continue
        else:
            unite(a[j],b[j],par,rank)
    for j in range(n):
        diff.add(find(j,par))
    if len(diff) == 1:
        continue
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for y in range(m)]
t = copy.copy(array)


def solver(start, array, visited, cnt):
    if visited[start]:
        return cnt
    else:
        visited[start] = True

    for i in array[start]:
        if len(set(visited)) == 1:
            return 1
        else:
            cnt = solver(i, array, visited, cnt)

    return cnt


res2 = 0
for i in range(m):
    tmp = array[:i] + array[i + 1:]
    modify = [[] for x in range(n + 1)]
    for value1, value2 in tmp:
        modify[value1].append(value2)
        modify[value2].append(value1)

    visited = [False if x != 0 and x != 1 else True for x in range(n + 1)]
    if not modify[1]:
        continue

    res = 0
    for i in modify[1]:
        res += solver(i, modify, visited, 0)
    else:
        res2 += 1 if res > 0 else 0

print(m - res2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[False for i in range(n)] for j in range(n)]
AB = []
for i in range(m):
    a,b = map(int, input().split())
    AB.append((a,b))
    graph[a-1][b-1] = True
    graph[b-1][a-1] = True
    
def dfs(x):
    if visited[x]:
        return
    visited[x] = True
    for i in range(n):
        if graph[x][i]:
            dfs(i)
            
ans = 0
for i in AB:
    graph[i[0]-1][i[1]-1] = graph[i[1]-1][i[0]-1] = False
    visited = [False for i in range(n)]
    dfs(0)
    check = True
    for j in range(n):
        if not visited[j]:
            check = False
    if not check:
        ans += 1
    graph[i[0]-1][i[1]-1] = graph[i[1]-1][i[0]-1] = True
print(ans)

Submission status: Accepted

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

cnt=0
def dfs(u):
  global cnt
  global visited
  visited[u]=True
  for v in edges[u]:
    if visited[v]==False:
      dfs(v)
  if all(visited):
    return 0
  else:
    return 1
ab=[]
for i in range(m):
  a,b=map(int,input().split())
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
  ab.append([a,b])
for i in range(m):
  visited=[False]*n
  a,b=ab[i]
  edges[a-1].remove(b-1)
  edges[b-1].remove(a-1)
  cnt+=dfs(0)
  edges[a-1].append(b-1)
  edges[b-1].append(a-1)
print(cnt)

Submission status: Accepted

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

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]

  def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

count = 0     
for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i!=j:
      uf.union(info[j][0],info[j][1])
  for k in range(n):
    for l in range(n): 
      if not uf.is_same(k,l):
        count =  count +1 
        break
      else:
        continue
      break
    else:
      continue
    break
print(count)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
    UF = UnionFind(n)
    use = ab[::]
    use.pop(i)
    for a, b in use:
        UF.union(a-1, b-1)
    if sum([j<0 for j in UF.parent])!=1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
E = [list(map(int,input().split())) for _ in range(M)]
from collections import defaultdict

ans=0
for i in range(M):
    d = defaultdict(list)
    for j in range(M):
        if i!=j:
            d[E[j][0]].append(E[j][1])
            d[E[j][1]].append(E[j][0])
    f = defaultdict(lambda: 0)
    f[1]=1
    que=d[1]
    while len(que)>0:
        tmp=[]
        for q in que:
            if f[q]==0:
                f[q]=1
                tmp+=d[q]
        que=tmp
    if len(f.keys())<N:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
for bridge in range(M):
    E = edges[0:bridge] + edges[bridge + 1:M]
    wf = [[1 for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if i == j:
                wf[i][j] = 0
            if (min(i, j), max(i, j)) in E:
                wf[i][j] = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for k in range(1, N + 1):
                if wf[j][k] > wf[j][i] + wf[i][k]:
                    wf[j][k] = wf[j][i] + wf[i][k]
    if wf[1][1:] != [0] * N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
E0 = [frozenset(map(int, input().split())) for _ in range(m)]
E = set(E0)
ans = 0

for e in E0:
    e = list(e)
    v0, v = e[0], e[1]

    now_path = [v0]
    branches = []
    history = {v0}

    for _ in range(n):
        branch_pts = [w for w in range(1, n+1) if
                      frozenset([now_path[-1], w]) in E and
                      frozenset([now_path[-1], w]) != frozenset(e) and
                      w not in history]
        if v in branch_pts:
            break
        branches.extend([(len(now_path)-1, w) for w in branch_pts])
        history |= set(branch_pts)
        if not branches:
            ans += 1
            break
        branch = branches.pop(-1)
        now_path = now_path[:branch[0]+1]
        now_path.append(branch[1])

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parent = [-1]*n
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def union(self, x,y):
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y:
            return False
        if self.parent[root_x] < self.parent[root_y]:
            self.parent[root_x] += self.parent[root_y]
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] += self.parent[root_x]
            self.parent[root_x] = root_y
        return True

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ans = 0
for i in range(m):
    UF = UnionFind(n)
    use = ab[::]
    use.pop(i)
    for a, b in use:
        UF.union(a-1, b-1)
    if sum([j<0 for j in UF.parent]) -1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and not visited[y]:
            visited[y] = True
            dfs(y, adj, visited)

def is_simply_connected(adj):
    n = len(adj)
    visited = [(i == 0) for i in range(n)]
    dfs(0, adj, visited)
    return False not in visited

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adj[a][b] = adj[b][a] = False
        if not is_simply_connected(adj):
            res += 1
        adj[a][b] = adj[b][a] = True
    print(res)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def is_simply_connected(adj):
    n = len(adj)
    visited = {0}  # O(log n). Use list instead.
    dfs(0, adj, visited)
    return len(visited) == n

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adj[a][b] = adj[b][a] = False
        if not is_simply_connected(adj):
            res += 1
        adj[a][b] = adj[b][a] = True
    print(res)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def is_simply_connected(adj):
    n = len(adj)
    visited = {0}
    dfs(0, adj, visited)
    return len(visited) == n

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for a, b in edges:
        adjc = deepcopy(adj)
        adjc[a][b] = False
        adjc[b][a] = False
        if not is_simply_connected(adjc):
            res += 1
    print(res)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

def dfs(x, adj, visited):
    for y, flag in enumerate(adj[x]):
        if flag and y not in visited:
            visited.add(y)
            dfs(y, adj, visited)

def main():
    n, m = map(int, input().split())
    adj = [[(i == j) for i in range(n)] for j in range(n)]
    edges = set()
    for i in range(m):
        a1, b1 = map(int, input().split())
        a = a1 - 1
        b = b1 - 1
        edges.add((a, b))
        adj[a][b] = True
        adj[b][a] = True

    res = 0
    for e in edges:
        adjc = deepcopy(adj)
        adjc[e[0]][e[1]] = False
        adjc[e[1]][e[0]] = False
        visited = {0}
        dfs(0, adjc, visited)
        if len(visited) < n:
            res += 1
    print(res)

main()

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1: return False
        # 併合
        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


def solve():
    [N, M] = [int(x) for x in input().split()]

    edges = []
    g = [[False] * N for _ in range(N)]
    for i in range(M):
        a, b = [int(x) for x in input().split()]
        edges.append((a-1, b-1))
        g[a-1][b-1] = g[b-1][a-1] = True

    ans = 0
    for i in range(len(edges)):
        uf = UnionFind(N)

        for j in range(len(edges)):
            e = edges[j]
            if i == j:
                # print("Remove {} -> {}".format(*e))
                continue
            uf.union(*e)

        n = len(set(uf.table))
        ans += n != 1

        # print(uf.table)
        # print(len(set(uf.table)))
        # print(any(uf.table))
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(u, g, visited):
    visited[u] = True

    for v in range(len(g)):
        if visited[v]:
            continue
        if g[u][v]:
            dfs(v, g, visited)


def solve():
    [N, M] = [int(x) for x in input().split()]

    import collections

    edges = []
    g = [[False] * N for _ in range(N)]
    for i in range(M):
        a, b = [int(x) for x in input().split()]
        edges.append((a-1, b-1))
        g[a-1][b-1] = g[b-1][a-1] = True

    ans = 0
    for e in edges:
        g[e[0]][e[1]] = g[e[1]][e[0]] = False

        # print(g)
        visited = [False] * N

        dfs(0, g, visited)
        # print(visited)
        ans += not all(visited)

        g[e[0]][e[1]] = g[e[1]][e[0]] = True
    return ans


def main():
    print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(v,e):
  for x in v:
    if len(e[x]) == 1:#端であるなら、プラス1して次へ
      y = e[x][0]
      v.remove(x)#returnで終わるから
      e[x] = []
      e[y].remove(x)
      return f(v,e)+1
  return 0 #端じゃないなら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 Queue
def is_bridge(_a, _b, neighbors, N, M):
    q = Queue.Queue()
    q.put(_a)
    used = {_a}
    for _ in range(M):
        if q.empty():
            break
        fr = q.get()
        for to, is_nei in enumerate(neighbors[fr]):
            if  is_nei and (fr != _a or to != _b) and to not in used:
                q.put(to)
                used.add(to)
    return len(used) < N


N, M = map(int, raw_input().split())
neighbors = [[False] * N for _ in range(N)]
ab = []
for _ in range(M):
    _a, _b = map(int, raw_input().split())
    _a -= 1
    _b -= 1
    neighbors[_a][_b] = True
    neighbors[_b][_a] = True
    ab.append((_a, _b))

res = 0
for _a, _b in ab:
    if is_bridge(_a, _b, neighbors, N, M):
        res += 1
print res

Submission status: Accepted

Solution code:
import Queue
def is_bridge(_a, _b, neighbors, M):
    q = Queue.Queue()
    q.put(_a)
    used = {_a}
    for _ in range(M):
        if q.empty():
            break
        fr = q.get()
        for to, is_nei in enumerate(neighbors[fr]):
            if  is_nei and (fr != _a or to != _b) and to not in used:
                q.put(to)
                used.add(to)
    return len(used) < N


N, M = map(int, raw_input().split())
neighbors = [[False] * N for _ in range(N)]
ab = []
for _ in range(M):
    _a, _b = map(int, raw_input().split())
    _a -= 1
    _b -= 1
    neighbors[_a][_b] = True
    neighbors[_b][_a] = True
    ab.append((_a, _b))

res = 0
for _a, _b in ab:
    if is_bridge(_a, _b, neighbors, N):
        res += 1
print res

Submission status: Accepted

Solution code:
def multival(): return map(int,input().split())
def data(N=1): return [list(map(int,input().split())) for _ in range(N)]
mod = 10**9 + 7
inf = float("inf")


N,M = multival()
nemat = [[0]*N for _ in range(N)]
ans = M
info = []
for _ in range(M):
    a,b = multival()
    a -= 1; b-= 1
    nemat[a][b] = 1
    nemat[b][a] = 1
    info.append([a,b])

def dfs(now,visited):
    visited[now] = True
    if all(visited):
        global ans
        ans -= 1
        return
    for ne in range(N):
        if nemat[now][ne] == 1 and visited[ne] is False:
            dfs(ne,visited)
    
for i,j in info:
    nemat[i][j] = 0
    nemat[j][i] = 0
    dfs(0,[False]*N)
    nemat[i][j] = 1
    nemat[j][i] = 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = list(map(int, input().split()))
li = []
for _ in range(m):
    li.append(list(map(int, input().split())))

ans = 0
for k in range(len(li)):
    li0 = li[:k] + li[k + 1:]
    # construct indirectional graphs
    edges = [[] for _ in range(n)]
    for i, j in li0:
        i -= 1
        j -= 1
        edges[i].append(j)
        edges[j].append(i)
    # check bridge
    S = deque()
    S.append(0)
    visited = set()
    while len(S) > 0:
        u = S.pop()
        visited.add(u)
        for v in edges[u]:
            if v not in visited:
                S.append(v)
    if len(visited) < n:
        ans += 1


print(ans)

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

n,m = (int(i) for i in input().split())
a = []
for i in range(m):
 tmp = list(int(i) for i in input().split())
 a.append(tmp)
ct = 0
for i in range(m):
  uf = UnionFind(n)
  for j in range(m):
    if i == j:
      nanban = j
    else:
      tmp1= a[j][0]
      tmp2= a[j][1]
      uf.union(tmp1,tmp2)
  c = a[nanban][0]
  d = a[nanban][1]
  if not uf.same_check(c,d):
   ct +=1
print(ct)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
E = {i:[] for i in range(N)}
mat = [[False for i in range(N)] for j in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
    mat[a][b] = True
    mat[b][a] = True
cnt = 0
for i in range(N):
    if sum(mat[i]) == 1:
        while True:
            if len(E[i]) != 1:
                break
            j = E[i][0]
            E[i].remove(j)
            E[j].remove(i)
            cnt += 1
            i = j
print(cnt)

Submission status: Accepted

Solution code:
# sys.stdin.readline()
from copy import deepcopy
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
GM = [[False]*N for _ in range(N)]
GL = []
for _ in range(M):
  a, b = list(map(int, input().split()))
  GM[a-1][b-1], GM[b-1][a-1] = True, True
  GL.append([a-1,b-1])
  
def DFS(v,g):
  visited[v] = True
  for i in range(N):
    if g[v][i] and not visited[i]:
      DFS(i,g)

ans = 0

for i in range(M):
  G = deepcopy(GM)
  G[GL[i][0]][GL[i][1]], G[GL[i][1]][GL[i][0]] = False, False
  visited = [False] * N
  DFS(0,G)
  
  flg = False
  for j in range(N):
    if not visited[j]:
      flg = True
      break
      
  if flg:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, size):
        self.table = [i for i in range(size)]

    def find(self, x):
        return self.table[x]

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

        if x1 == y1:
            return False

        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


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

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

mat = [[0]*N for _ in range(N)]
for s, g in edges:
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0

for i in range(M):
    uni = UnionFind(N)

    for j in range(M):
        if i != j:
            uni.union(edges[j][0], edges[j][1])

    if not all(uni.find(0) == uni.find(x) for x in range(N)):
        ans += 1
print(ans)

Submission status: Accepted

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

nodes = [0]*N

mat = [[0]*N for _ in range(N)]

for s, g in edges:
    nodes[s] += 1
    nodes[g] += 1
    mat[s][g] = 1
    mat[g][s] = 1

ans = 0


def check(nodes):
    return all(n != 1 for n in nodes)


ans = 0
while not check(nodes):
    for i in range(N):
        if nodes[i] == 1:
            for j in range(N):
                if mat[i][j]:
                    mat[i][j] = 0
                    mat[j][i] = 0
                    ans += 1
                    nodes[i] -= 1
                    nodes[j] -= 1
                    break
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
G = [[False]*(N+1) for _ in range(N+1)]

for elem in AB:
    a, b = elem
    G[a][b] = True
    G[b][a] = True

used = [False] * (N+1)


def dfs(v):
    ret = 1
    used[v] = True
    for nv in range(1, N+1):
        if G[v][nv] and not used[nv]:
            ret += dfs(nv)
    return ret


ans = 0
for elem in AB:
    a, b = elem
    G[a][b] = False
    G[b][a] = False
    for j in range(1, N+1):
        used[j] = False
    if dfs(1) != N:
        ans += 1
    G[a][b] = True
    G[b][a] = True
print(ans)

Submission status: Accepted

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def renketu(Town):
    cnt = 0
    for i in range(1,len(Town.par)):
        for j in range(1,i):
            if not Town.same_check(i,j):
                return True
    return False

if __name__ == '__main__':
    N,M = list(map(int,input().split()))
    # print(Town.par)
    bridge = [list(map(int,input().split())) for i in range(M)]
    cnt = 0
    for kesu in range(M):
        Town = UnionFind(N)
        for i,(x,y) in enumerate(bridge):
            if i != kesu:
                Town.union(x,y)
        if renketu(Town):
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
# ABC 075
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def getIntFromRows(n): return [int(input()) for i in range(n)]
def getIntMat(n):
    mat = []
    for i in range(n): mat.append(getIntList())
    return mat
def zeros(n): return [0 for i in range(n)]
def zeros2(n, m): return [[0 for i in range(m)] for j in range(n)]

debug = True
def db(x): 
    if debug: print(x)

debug = False
n,m = getIntList()
a,b = zeros(m),zeros(m)
org = zeros(m)

for i in range(m):    org[i] = getIntList()

db(('org graph',org))
count = 0

def find(graph, fromNode, toNode, route): # -1: NG, >=OK、評価値
    db(('f-t',fromNode, toNode))
    if fromNode in route: return -1
    else:
        route = route + [fromNode]
        if fromNode==toNode: return 0
        for edge in graph:
            if edge[0]==fromNode:  # graphのソート、一旦fromが見つかった後の中断
                val = find(graph, edge[1], toNode, route)
                db(('found', route, edge[1], toNode))
                if val==0: return 0
        db(('cannot',fromNode, toNode))
        return -1
    
graph = zeros((m-1)*2)
count = 0
for i in range(m):
    new = org[:i] + org[i+1:]
    db(('cut',org[i]))
    db(('new',new))
    for j in range(m-1):
        graph[j*2] = new[j]
        graph[j*2+1] = [new[j][1], new[j][0]]
    graph.sort()
    db(('new graph',graph))
    route = []
    if find(graph, org[i][0], org[i][1], route)<0: count += 1
print(count)

def connected(graph, node): # 全ノードに行けるか
    db(('check node', node))
    for i in range(n):
        if i==node: continue
        found = False
        for e in graph:
            #db(('edge',e))
            if e[0]==node and e[1]==i: 
                found = True
                break
        if not found: return False
    db(('ok node', node))
    return True