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:
def DFS(N, copyedge):
    matrix = [[] for i in range(N)]
    for a, b in copyedge:
        matrix[a] += [b]
        matrix[b] += [a]
    check = [True]*N
    check[0] = False
    Que = [0]
    
    while len(Que) != 0:
        now = Que.pop()
        for j in matrix[now]:
            if check[j] == True:
                check[j] = False
                Que.append(j)
    if check == [False]*N:
        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:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  G[a - 1].append([i, b - 1])
  G[b - 1].append([i, a - 1])
cnt = 0
for i in range(M):
  D = [N] * N
  D[0] = 0
  Q = [0]
  while Q:
    s = Q[0]
    Q = Q[1:]
    for idx, adj in G[s]:
      if idx != i and D[adj] == N:
        D[adj] = D[s] + 1
        Q.append(adj)
  cnt += 1 if max(D) == N else 0
print(cnt)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

def dfs(i):
    for j in range(1,N+1):
        if visit[j]:
            continue
        if not path[i][j]:
            continue
        visit[j] = True
        X = dfs(j)
    return visit

N, M = inpl()
path = [[False for _ in range(N+1)] for i in range(N+1)]
visit = [False for _ in range(N+1)]
visit[0] = visit[1] = True
H = []
for i in range(M):
    a,b = inpl()
    path[a][b] = path[b][a] = True
    H.append((a,b))
    
ans = 0    
for st,en in H:
    path[st][en] = path[en][st] = False
    if False in dfs(1):
        ans += 1
    path[st][en] = path[en][st] = True
    for i in range(2,N+1):
        visit[i] = False
print(ans)

Submission status: Accepted

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

s = [[] for i in range(n)]
for a, b in ab:
    s[a - 1].append(b - 1)
    s[b - 1].append(a - 1)

route = [[x, 0] for x in s[0]]
c = [[] for i in range(n)]
while 1:
    next = []
    for x in route:
        for y in s[x[0]]:
            if y == x[1]:
                continue
            if y in x:
                #print(x, y, c)
                if y not in c[x[0]]:
                    c[x[0]].append(y)
                if x[0] not in c[y]:
                    c[y].append(x[0])
                for i in range(len(x) - 1):
                    if x[i + 1] not in c[x[i]]:
                        c[x[i]].append(x[i + 1])
                    if x[i] not in c[x[i + 1]]:
                        c[x[i + 1]].append(x[i])
                    if x[i + 1] == y:
                        break
            else:
                next.append([y] + x)
    if len(next) == 0:
        break
    route = [] + next

#print(s)
#print(c)

ans = 0
for i in range(n):
    ans += len(s[i]) - len(c[i])

print(ans // 2)

Submission status: Accepted

Solution code:
def dps(now,i,j,arr,node):
    for x in arr[now]:
        if (now==i and x==j) or (now==j and x==i):
            continue
        if node[x]==0:
            node[x]=1
            dps(x,i,j,arr,node)

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

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

ans=0
for i,x in enumerate(arr):
    for j in x:
        node=[0 for _ in range(N)]
        dps(0,i,j,arr,node)
        if sum(node)!=N:
            ans+=1
print(ans//2)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
a=[]
b=[]
g=[[] for i in range(n)]
for i in range(m):
  ai, bi=map(int, input().split())
  ai-=1
  bi-=1
  g[ai].append(bi)
  g[bi].append(ai)
  a.append(ai)
  b.append(bi)
used=[False for i in range(n)]
dame1=0
dame2=0
def dfs(x):
  used[x]=True
  for y in g[x]:
    if dame1==x and dame2==y:
      continue
    if not used[y]:
      dfs(y)
ans=0
for i in range(m):
  used=[False for i in range(n)]
  dame1=a[i]
  dame2=b[i]
  dfs(a[i])
  if not used[b[i]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
a=[]
b=[]
g=[]
for i in range(n):
  g.append([])
for i in range(m):
  ai, bi=map(int, input().split())
  ai-=1
  bi-=1
  g[ai].append(bi)
  g[bi].append(ai)
  a.append(ai)
  b.append(bi)
used=[]
for i in range(n):
  used.append(False)
dame1=0
dame2=0
def dfs(x):
  used[x]=True
  for y in g[x]:
    if dame1==x and dame2==y:
      continue
    if not used[y]:
      dfs(y)
  return
ans=0
for i in range(m):
  for j in range(n):
    used[j]=False
  dame1=a[i]
  dame2=b[i]
  dfs(a[i])
  if not used[b[i]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
a=[]
b=[]
g=[]
for i in range(n):
  g.append([])
for i in range(m):
  ai, bi=map(int, input().split())
  ai-=1
  bi-=1
  g[ai].append(bi)
  g[bi].append(ai)
  a.append(ai)
  b.append(bi)
used=[]
for i in range(n):
  used.append(False)
dame1=0
dame2=0
def dfs(x):
  used[x]=True
  for y in g[x]:
    if (dame1==x and dame2==y) or (dame1==y and dame2==x):
      continue
    if not used[y]:
      dfs(y)
  return
ans=0
for i in range(m):
  for j in range(n):
    used[j]=False
  dame1=a[i]
  dame2=b[i]
  dfs(a[i])
  if not used[b[i]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

map_org = []
for i in range(N):
    map_org.append([0 for _ in range(N)])

for a,b in ab:
    map_org[a-1][b-1] = 1
    map_org[b-1][a-1] = 1

def dfs(v):
    visited[v] = 1
    for i in range(N):
        if map_org[v][i] == 1:
            if visited[i] == 0:
                dfs(i)

bridge_cnt = 0
for i in range(M):
    visited = [0 for _ in range(N)]
    del_a,del_b = ab[i]
    map_org[del_a-1][del_b-1] = 0
    map_org[del_b-1][del_a-1] = 0
    dfs(0)
    if min(visited) == 0:
        bridge_cnt += 1
    map_org[del_a-1][del_b-1] = 1
    map_org[del_b-1][del_a-1] = 1


print(bridge_cnt)

Submission status: Accepted

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

def Bridge(a, b):
    Cost = [51 for i in range(N)]
    Cost[a] = 0
    Q = [a]
    while Q:
        now = Q.pop(0)
        for next in E[now]:
            if now != a or next!=b:
                if Cost[next] == 51:
                    Cost[next] = Cost[now] + 1
                    Q.append(next)
    if Cost[b] == 51:
        return True
    else:
        return False

ans = 0
for r in R:
    if Bridge(r[0], r[1]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 13 12:14:21 2018
ABC075C
@author: maezawa
"""

def dfs(now, visited):
    visited.add(now)
    if len(visited) == n:
        return True
    ans = False
    for nextnode in adj[now]:
        if nextnode in visited:
            continue
        if dfs(nextnode, visited):
            ans = True
    return ans
        

def is_bridge(cur_edge):
    start = cur_edge[0]
    visited = set([])
    adj[cur_edge[1]].remove(start)
    adj[start].remove(cur_edge[1])
    if dfs(start,visited):
        ans = False
    else:
        ans = True
    adj[cur_edge[1]].append(start)
    adj[start].append(cur_edge[1])
    return ans
    
    
n, m = list(map(int, input().split()))
adj = [[] for _ in range(n+1)]
edges = []
for _ in range(m):
    ai, bi = list(map(int, input().split()))
    adj[ai].append(bi)
    adj[bi].append(ai)
    edges.append([ai, bi])

#print(adj)

cnt = 0
for edge in edges:
    if is_bridge(edge):
        #print(edge)
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans = 0
for a, b in edges:
    cur_g = [x.copy() for x in g]
    cur_g[a].remove(b)
    cur_g[b].remove(a)
    visited = [False] * (N + 1)
    dfs_stack = [1]
    while dfs_stack:
        s = dfs_stack.pop()
        visited[s] = True
        for t in cur_g[s]:
            if not visited[t]:
                dfs_stack.append(t)
    if not all(visited[1:]):
        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)]
adjs = [list() for _ in range(N)]

def search(i, mem, a, b):
    if mem[i]:
        return 0
    cnt = 1
    mem[i] = True
    for x in adjs[i]:
        if (i == a and b == x) or (i == b and x == a):
            continue
        cnt += search(x, mem, a,b)
    return cnt

for a, b in edges:
    adjs[a-1].append(b-1)
    adjs[b-1].append(a-1)
ans = 0
for a, b in edges:
    mem = [False for _ in range(N)]
    if search(0, mem, a-1, b-1) < N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
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]

    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

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
      
n,m=map(int, input().split())
path=[]
for i in range(m):
    a,b=map(int, input().split())
    path.append([a-1,b-1])
    
count=0
for i in range(m):
    path2=path[:]
    path2.pop(i)
    uf1=UnionFind(n)
    for a,b in path2:
        uf1.union(a,b)
    if not uf1.is_same(path[i][0],path[i][1]): count+=1
print(count)

Submission status: Accepted

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


def dfs(v, pre, s, ng):
    if used[v]:
        return
    used[v] = 1
    s.add(v)
    for u in G[v]:
        if u == pre:
            continue
        if (u, v) != ng and (v, u) != ng:
            dfs(u, v, s, ng)
    return


num = 0
for i in E:
    used = [0] * N
    s = set()
    dfs(0, -1, s, i)
    if len(s) == N:
        num += 1

print(M - num)

Submission status: Accepted

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

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


def dfs(s, a, b):
    flag[s] = 1
    for v in graph[s]:
        if s == a and v == b or s == b and v == a:
            continue
        if flag[v] == 1:
            continue
        dfs(v, a, b)

ans = 0
for i in range(n):
    for v in graph[i]:
        flag = [0 for i in range(n)]
        dfs(0, i, v)
        num = 0
        for j in flag:
            if j == 0:
                num = 1
        if num == 1:
            ans += 1
print(ans//2)

Submission status: Accepted

Solution code:

import copy
def fa():  # final answer
    global ans
    print(ans)


def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

def check_bridge(n, a, b, edge):
    edge[a-1][b-1] = 0
    edge[b-1][a-1] = 0
    link = [1]
    stack = []
    for i in range(n):
        if edge[0][i] == 1:
            link.append(i+1)
            stack.append(i+1)

    while(stack != []):
        dep = stack[0]
        for i in range(n):
            if edge[dep-1][i] == 1:
                if i+1 not in link:
                    link.append(i+1)
                    stack.append(i+1)
        stack = stack[1:]

    if len(link) == n:
        return True
    else:
        return False

n,m = getNM()
edge = [[0 for i in range(n)] for j in range(n)]
pile = []
for i in range(m):
    a,b = getNM()
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1
    pile.append((a,b))

ans = 0
for pair in pile:
    a, b = pair[0], pair[1]
    edge2 = copy.deepcopy(edge)
    if check_bridge(n, a, b, edge2) == False:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def dfs(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0,start)]
    
    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node],nex_node))
                
    return dist

n,m = li()
edges = []
INF = float("inf")

for _ in range(m):
    a,b = li_()
    edges.append((a,b))
    
ans = 0
for i in range(m):
    graph = graph = [[] for _ in range(n)]
    for j in range(m):
        if i != j:
            graph[edges[j][0]].append((1,edges[j][1]))
            graph[edges[j][1]].append((1,edges[j][0]))
            
    dist = dfs(graph, n, 0)
    
    if INF in dist:
        ans += 1
        
        
print(ans)

Submission status: Accepted

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

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j,(a,b) in enumerate(es):
        if i == j: continue
        if uf.is_same(a,b): continue
        uf.unite(a,b)
    u,v = es[i]
    if not uf.is_same(u,v):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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


def dfs(u, graph, visited):
    visited[u] = True
    for v in graph[u]:
        if not visited[v]:
            dfs(v, graph, visited)


cnt = 0
for i in range(M):
    idx = list(range(0, i)) + list(range(i + 1, M))
    graph = defaultdict(list)
    for u, v in zip(a[:i] + a[i + 1:], b[:i] + b[i + 1:]):
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * N
    dfs(u, graph, visited)
    if False in visited:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class uf:
	def __init__(self, n):
		self.size = n
		self.parents = [i for i in range(n)]
		self.ranks = [0 for i in range(n)]
	def find(self, x):
		if x == self.parents[x]:
			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.ranks[x] > self.ranks[y]:
			self.parents[y] = x
		else:
			self.parents[x] = y
		if self.ranks[x] == self.ranks[y]:
			self.ranks[y] += 1

ans = 0
n,m = map(int,input().split())
t = [uf(n) for i in range(m)]
g = [list(map(lambda x: int(x)-1,input().split())) for i in range(m)]
for i in range(m):
	for e in g:
		if e == g[i]:
			continue
		t[i].union(e[0],e[1])
	if len(set([t[i].find(j) for j in range(n)])) > 1:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
#ABC075C
N, M=map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
visit_list=[0]*N
ans=0
#i番目の2次元配列を除く配列を使って、島jとその隣の未訪問の島にチェックを入れる
def follow(i, ab, j):
    visit_list[j-1]=1
    for k in range(M):
        if k!=i:
            if ab[k][0]==j:
                if visit_list[ab[k][1]-1]==0:
                    follow(i, ab, ab[k][1])
            if ab[k][1]==j:
                if visit_list[ab[k][0]-1]==0:
                    follow(i, ab, ab[k][0])
for i in range(M):
    visit_list=[0]*N
    follow(i, ab, 1)
    if sum(visit_list)!=N:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy

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

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path)

nodes = []
for i in range(N):
    nodes.append(Node(i))

paths = []
for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split() ]
    paths.append([from_id, to_id])
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(passed_nodes):
    if len(passed_nodes) == N:
        return True
    else:
        return False

def go_child(id_new, passed_nodes):
    passed_nodes.append(id_new)
    if if_all_passed(passed_nodes):
        return True

    for i in nodes[id_new].path:
        if not i in passed_nodes:
            if go_child(i, passed_nodes):
                return True
    return False

count = 0
for ids in paths:
    nodes[ids[0]].path.remove(ids[1])
    nodes[ids[1]].path.remove(ids[0])
    if not go_child(0, []):
        count += 1
    nodes[ids[0]].path.append(ids[1])
    nodes[ids[1]].path.append(ids[0])

print(count)

Submission status: Accepted

Solution code:
import sys
import itertools

N, M = [int(i) for i in sys.stdin.readline().split()]
edges = [[] for _ in range(N)]
for l in sys.stdin.readlines():
  a, b = [int(i)-1 for i in l.strip().split()]
  edges[a].append(b)
  edges[b].append(a)

def flatten(l):
  return list(itertools.chain.from_iterable(l))

def is_spanning_tree(edges):
  # list of tuple to 2d-list
  new_edges = [[] for _ in range(N)]
  for a, b in edges:
    new_edges[a].append(b)
    new_edges[b].append(a)
  edges = new_edges
  nodes = set([0])
  next_node_candidates = set(flatten([edges[n] for n in nodes]))
  while next_node_candidates:
    nodes.add(list(next_node_candidates)[0])
    next_node_candidates = set(flatten([edges[n] for n in nodes]))
    next_node_candidates = [x for x in next_node_candidates if x not in nodes] #まだ追加されていないcandidate
  return True if len(nodes) == N else False

cnt = 0
edges = flatten([[(i, j) for j in edges[i] if i>=j] for i in range(N)])
incomplete_graphs = [[edges[j] for j in range(len(edges)) if i != j] for i in range(len(edges))]
spanning_trees = [1 if not is_spanning_tree(graph) else 0 for graph in incomplete_graphs]
print(sum(spanning_trees))

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy
import heapq
import math

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():

    global count
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [long(input_raw[0]), long(input_raw[1])]
    adj_list = {}
    edge_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [long(input_raw[0]), long(input_raw[1])]
        if a not in adj_list:
            adj_list[a] = [b]
        else:
            adj_list[a].append(b)

        if b not in adj_list:
            adj_list[b] = [a]
        else:
            adj_list[b].append(a)
        edge_list.append((a, b))
    

    count = 0
    for i in range(M):
        (a, b) = edge_list[i]
        is_visit = [False for j in range(N + 1)]
        visit_count = 0
        q = deque([1])
        while 1:
            #print q
            if len(q) <= 0: break;
            
            nd = q.popleft()
            visit_count += 1
            is_visit[nd] = True
            for adj in adj_list[nd]:
                if (nd, adj) != (a, b) and (nd, adj) != (b, a) and is_visit[adj] == False:
                    q.append(adj)
                    is_visit[adj] = True
        if visit_count < N:
            count += 1


    print count



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import math

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

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

E = np.zeros((N, N), dtype=int)

for m in range(M):
    s, t = map(int, input().split())
    s = s-1
    t = t-1
    E[s][t] = 1
    E[t][s] = 1

# print(E)
    
bridges = set()
TIME = 0
    
def bridgeN(n, visited, parent, low, dis):
    global TIME
    visited[n] = 1
    dis[n] = TIME
    low[n] = TIME
    TIME += 1

    # print('time', TIME)

    # print('n=', n)
    # print('visited=', visited)
    
    for v in range(N):
        if E[n][v] == 0:
            continue
        if visited[v] == 1:
            if v != parent[n]:
                low[n] = min(low[n], dis[v])
            continue

        # print('visited[', v, ']=', visited[v])
        
        parent[v] = n
        bridgeN(v, visited, parent, low, dis)

        low[n] = min(low[n], low[v])

        if low[v] > dis[n]:
            if v <= n:
                bridges.add((v, n))
            else:
                bridges.add((n, v))
                

def bridge(E):
    visited = np.zeros(N, dtype=int)
    dis = np.full_like(visited, N*N*10)
    low = np.full_like(visited, N*N*10)
    parent = np.full_like(visited, -1)

    for n in range(N):
        if visited[n] == 0:
            bridgeN(n, visited, parent, low, dis)

bridge(E)
nBridges = len(bridges)
# print(bridges)

print(nBridges)

Submission status: Accepted

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

inf = float('inf')

import heapq
def dijkstra(adj, n, st=1):
    dj = [inf] * (n + 1)
    dj[st] = 0
    q = []
    heapq.heappush(q, (0, st))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[fn] + lc < dj[tn]:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

ans = 0
ab = [[int(x) for x in input().split()] for _ in range(M)]
for i in range(len(ab)):
    adj = dict((x, []) for x in range(N + 1))
    for j, (a, b) in enumerate(ab):
        if i == j: continue
        adj[a].append((b, 1))
        adj[b].append((a, 1))
    costs = dijkstra(adj, N)
    ans += any(x == inf for x in costs[1:])
print(ans)

Submission status: Accepted

Solution code:
"""
C - Bridge
とりあえず、グラフ構造を作る
そして、全通りの辺を抜いてみて、探索を行うことで確かめる
"""

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

pairs = []
for side in range(M):
    pair = []
    for side in input().split():
        pair.append(int(side))
    pairs.append(pair)

graph = [[0 for i in range(N)] for j in range(N)]

# グラフ構築
for pair in pairs:
    a = pair[0]
    b = pair[1]

    # 無向グラフ
    graph[a - 1][b - 1] += 1
    graph[b - 1][a - 1] += 1

def bfs(graph, start):
    queue = []
    exist_v = [False for v in range(N)]
    exist_v[start] = True
    queue.append(start)

    # Q が殻ではない
    while queue:
        # 現在の場所
        v = queue.pop(0)
        
        # vに接続している頂点
        for i in range(N):
            # vにつながっているとき
            if graph[v][i] != 0:
                if exist_v[i] is False:
                    #print("頂点に到達しました", i+1)
                    exist_v[i] = True
                    queue.append(i)
    
    # 行けなかった漏れがあるなら
    for exist in exist_v:
        if exist is False:
            return False
    
    return True

cnt = 0
for pair in pairs:
    a = pair[0]
    b = pair[1]
    #print(a, b, "を抜いてみる")

    # 辺を試しに切る
    graph[a - 1][b - 1] -= 1
    graph[b - 1][a - 1] -= 1
    
    if bfs(graph, 0) is False:
        cnt += 1

    # もとに戻す
    graph[a - 1][b - 1] += 1
    graph[b - 1][a - 1] += 1

print(cnt)

Submission status: Accepted

Solution code:

cnt = 0
def dfs(g , start,N):
    global cnt
    visited = [False for i in range(N)]
    stack =[]
    stack.append(start)

    while stack:
        v = stack.pop()
        visited[v] = True

        for i in range(N):
            if g[v][i] == 1 and visited[i] ==False:
                stack.append(i)

    for i in range(N):
        if visited[i] == False:
            cnt += 1
            break


N,M = map(int,input().split())
g = [ [0 for i in range(N)] for j in range(N)]
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
    g[a[i]][b[i]] += 1
    g[b[i]][a[i]] += 1

for i in range(M):

    g[a[i]][b[i]] -= 1
    g[b[i]][a[i]] -= 1

    dfs(g,0,N)

    g[a[i]][b[i]] += 1
    g[b[i]][a[i]] += 1

print(cnt)

Submission status: Accepted

Solution code:
f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]


class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

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

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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n,m = f()
E = []
for _ in range(m):
    E.append(f_())

ans = 0
for edge in E:
    e = [i for i in E if not i == edge]
    u = UnionFind(n)
    for a,b in e:
        u.unite(a,b)

    f = False
    k = u.find(0)
    for i in range(n):
        if u.find(i) is not k:
            f = True
            break
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
a = [input().rstrip().split() for j in range(m)]

graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph

def DFS(v,visited):
    visited[v]=True
    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue
        DFS(i,visited)


cnt2 = 0
for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=False
    # print(graph)
    #始点が1とは限らない
    visited=[False]*n
    DFS(0,visited)
    # print(visited)
    if visited.count(False)!=0:
        cnt2 += 1
    graph[x][y]=graph[y][x]=True


print(cnt2)

Submission status: Accepted

Solution code:
from collections import deque
n, m = list(map(int, input().split()))
path = {}
ab = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    a, b = ab[i]
    if not a in path.keys():
        path[a] = [b]
    else:
        path[a].append(b)
    if not b in path.keys():
        path[b] = [a]
    else:
        path[b].append(a)

ans = 0
for i in range(m):
    a_tar, b_tar = ab[i]
    visit = [True] + [False]*n
    que = deque([1])
    while len(que) > 0:
        node = que.popleft()
        visit[node] = True
        for node_next in path[node]:
            if [node, node_next] == [a_tar, b_tar] or [node, node_next] == [b_tar, a_tar]:
                continue
            if visit[node_next]:
                continue
            que.append(node_next)
    if False in visit:
        ans += 1
print(ans)

Submission status: Accepted

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

def DFS(ab):
    S=ab[0][0]
    graph=[[0 for i in range(N)] for j in range(N)]
    for i in range(len(ab)):
        graph[(ab[i][0]-1)][(ab[i][1]-1)]=1
        graph[(ab[i][1]-1)][(ab[i][0]-1)]=1
    reached=[0 for _ in range(N)]
    Stack=[S]
    reached[S-1]=1
    while Stack:
        h=Stack.pop()
        for i in range(N):
            if graph[h][i]==1:
                if not(reached[i-1]):
                    Stack.append(i)
                    reached[i-1]=1
    return(sum(reached))

ans=0
for i in range(M):
    a=ab[:i]+ab[i+1:]
    if DFS(a)!=N:
        ans+=1
print(ans)