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())
Edge = [list(map(int,input().split())) for i in range(M)]


def dfs(i):
    visited.add(i)
    for k in From[i]:
        if k not in visited:
            dfs(k)
    for k in To[i]:
        if k not in visited:
            dfs(k)

def bridge(j):
    for i in Edge:
        if i == j:
            continue
        else:
            From[i[0]-1].append(i[1]-1)
            To[i[1]-1].append(i[0]-1)
    dfs(0)
    return True if visited.__len__() != N else False
ans = 0
for j in Edge:
    From = [[] for i in range(N)]
    To = [[] for i in range(N)]
    visited = set()
    ans += bridge(j)
    #print(From)
    #print(To)
    #print(visited)
print(ans)

Submission status: Accepted

Solution code:
class Graph:
    def __init__(self):
        self.g = {}
        self.node = set()

    def addEdge_single(self, x, y, w):
        self.g[(x, y)] = w
        self.node.add(x)
        self.node.add(y)

    def addEdge(self, x, y, w):
        self.addEdge_single(x, y, w)
        self.addEdge_single(y, x, w)

    def dijkstra(self, start):
        open = {start: 0}
        closed = {}
        prev = {start: -1}
        while len(open) > 0:
            x = Graph.select_min(open)
            m = open[x]
            del open[x]
            closed[x] = m
            for (y, w) in self.edge(x):
                if y in open:
                    if open[y] > m + w:
                        open[y] = m + w
                        prev[y] = x
                elif y not in closed:
                    open[y] = m + w
                    prev[y] = x
            # print("open:  {}".format(open))
            # print("closed:{}".format(closed))
            # print("prev:  {}".format(prev))
            # print("-----")
        return closed, prev

    @staticmethod
    def select_min(S):
        m = -1
        for a in S:
            if m == -1 or m > S[a]:
                x = a
                m = S[a]
        return x

    def edge(self, x):
        G = self.g
        return [(b, G[(a, b)]) for (a, b) in G if a == x]


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

AB = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a, b))

ans = 0
for i in range(M):
    g = Graph()
    for j in range(M):
        if i != j:
            g.addEdge(AB[j][0], AB[j][1], 1)
    w, p = g.dijkstra(1)
    if len(w) != N:
        ans += 1
    # print("w:{}, len:{}".format(w, len(w)))

print(ans)

Submission status: Accepted

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

G = [set() for _ in range(N)]
a = set()
for ab in AB:
    G[ab[0]].add(ab[1])


def find(a, x):
    stack = []
    while a[x] != x:
        x = a[x]
        stack += [x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    a[x] = a[y] = min(x, y)


ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if j in G[i]:
            Gn = copy.deepcopy(G)
            Gn[i].discard(j)
            a = [i for i in range(N)]
            for k in range(N - 1):
                for l in Gn[k]:
                    unite(a, k, l)
            par = set()
            for k in range(N):
                par.add(find(a, k))
            if len(par) > 1:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

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

ans = 0
for i in range(M) :
    Matrix_duplicated = deepcopy(Matrix)
    a,b = Path[i]
    Matrix_duplicated[a][b] = False
    Matrix_duplicated[b][a] = False
    Visited = []
    Queue = deque([0])
    while Queue :
        now = Queue.popleft()
        Visited.append(now)
        for i in range(N) :
            if Matrix_duplicated[now][i] :
                Matrix_duplicated[now][i] = False
                Matrix_duplicated[i][now] = False
                Queue.append(i)
    if len(list(set(Visited))) != N :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

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

INF = 63
ans = 0
for i in range(M) :
    Matrix_duplicated = deepcopy(Matrix)
    a,b = Path[i]
    Matrix_duplicated[a][b] = False
    Matrix_duplicated[b][a] = False
    Distance = [INF for i in range(N)]
    Distance[0] = 0
    Queue = deque([0])
    while Queue :
        now = Queue.popleft()
        for i in range(N) :
            if Matrix_duplicated[now][i] :
                Matrix_duplicated[now][i] = False
                Matrix_duplicated[i][now] = False
                Distance[i] = min(Distance[now]+1, Distance[i])
                Queue.append(i)
    if INF in Distance :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy

N,M = map(int,input().split())
Matrix = [[False for x in range(N)] for y in range(N)]

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

for i in range(M) :
    a,b = Path[i]
    Matrix[a][b] = True
    Matrix[b][a] = True
    
ans = 0
for i in range(M) :
    a,b = Path[i]
    Matrix_ = deepcopy(Matrix)
    Matrix_[a][b] = False
    Matrix_[b][a] = False
    INF = 63
    Distance = [INF for i in range(N)]
    Distance[0] = 0
    
    QUEUE = deque([0])
    while QUEUE :
        now = QUEUE.popleft()
        
        for i in range(N) :
            if Matrix_[now][i] :
                Matrix_[now][i] = False
                Matrix_[i][now] = False
                Distance[i] = min(Distance[now]+1,Distance[i])
                QUEUE.append(i)
    #print(Distance)
    if (INF in Distance) :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m = LI()
edge = [LI() for _ in range(m)]


def dfs(s):
    q = deque([s])
    visited = set()

    while q:
        curr = q.pop()
        visited.add(curr)
        for next in G[curr]:
            if next in visited:
                continue
            q.append(next)

    return True if len(visited) == n else False


ans = 0
for i in range(m):
    G = defaultdict(list)
    for j, e in enumerate(edge):
        if i == j:
            continue
        a, b = e
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    ans += 0 if dfs(0) else 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = 0
dis = [[0] * N for _ in range(N)]
info = []
for i in range(M):
    a,b = map(int,input().split())
    info.append([a-1,b-1])
    dis[a-1][b-1] = 1
    dis[b-1][a-1] = 1

def dfs(p):
    visited[p] = True
    for i in range(N):
        if dis[p][i] == 1 and visited[i] is False:
            dfs(i)

def check(start,n):
    global visited
    visited = [False] * N
    a = info[n][0]
    b = info[n][1]
    dis[a][b] = 0
    dis[b][a] = 0
    dfs(start)
    if set(visited) != {True}:
        global ans 
        ans += 1
    dis[a][b] = 1
    dis[b][a] = 1

for i in range(M):
    check(0,i)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = 0
dis = [[] for _ in range(N)]
info = []
for i in range(M):
    a,b = map(int,input().split())
    info.append([a-1,b-1])
    dis[a-1].append(b-1)
    dis[b-1].append(a-1)

def dfs(p):
    visited[p] = True
    for d in dis[p]:
        if visited[d] is False:
            dfs(d)

def check(start,n):
    global visited
    visited = [False] * N
    a = info[n][0]
    b = info[n][1]
    dis[a].remove(b)
    dis[b].remove(a)
    dfs(start)
    if set(visited) != {True}:
        global ans 
        ans += 1
    dis[a].append(b)
    dis[b].append(a)

for i in range(M):
    check(0,i)

print(ans)

Submission status: Accepted

Solution code:
def root(nodes,x):
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = root(nodes,nodes[x])
        return nodes[x]

def unite(nodes,x,y):
    root_x, root_y = root(nodes,x) , root(nodes,y)
    if root_x != root_y:
        nodes[root_x] = root_y

def is_same(nodes,x,y):
    return root(nodes,x) == root(nodes,y)


N,M = list(map(int,input().split()))
data = [[0 for s in range(2)] for k in range(M)]
for i in range(M):
    temp = input().split()
    data[i][0] = int(temp[0])-1
    data[i][1] = int(temp[1])-1
    
sum = 0

for i in range(M):
    nodes = [-1]*(N)
    for j in range(M):
        if j != i:
            unite(nodes,data[j][0],data[j][1])
    for k in range(1,N):
        if is_same(nodes,k-1,k):
            continue
        else:
            sum += 1
            break

print(sum)

Submission status: Accepted

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

def isbridge(j):
    G=[set() for i in range(N)]
    for i in range(M):
        if i==j:
            continue
        G[a[i]].add(b[i])
        G[b[i]].add(a[i])
    q=queue.Queue()
    reached=[0 for i in range(N)]
    q.put(0)
    reached[0]=1
    while(not(q.empty())):
        r=q.get()
        reached[r]=1
        for p in G[r]:
            if reached[p]==0:
                q.put(p)
    if sum(reached)==N:
        return False
    else:
        return True

ans=0
for i in range(M):
    if isbridge(i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a = []
b = []
for i in range(m):
    tmp = list(int(i) for i in input().split())
    a.append(tmp[0])
    b.append(tmp[1])
next = list([] for i in range(n))
for i in range(1,n+1):
    for j in range(m):
        if a[j]==i:
            next[i-1].append(b[j])
        elif b[j]==i:
            next[i-1].append(a[j])
cut = True
while cut:
    cut = False
    for i in range(n):
        if len(next[i])==1:
            if i+1 in next[next[i][0]-1]:
                next[next[i][0]-1].remove(i+1)
                cut = True
count = 0
for i in range(n):
    if len(next[i])==1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
a = [None]*m;b = [None]*m
ans = 0
for i in range(m):
    a[i],b[i] = map(int,input().split())
for i in range(m):
    check = [False]*n
    a_ls = list(a);b_ls = list(b)
    del a_ls[i],b_ls[i]
    deq = deque()
    num = 1
    deq.append(1)
    check[0] = True
    while not not deq:
        num = deq.pop()
        for i in range(m-1):
            if a_ls[i] == num:
                if check[b_ls[i]-1] == False:
                    deq.append(b_ls[i])
                    check[b_ls[i]-1] = True
            if b_ls[i] == num:
                if check[a_ls[i]-1] == False:
                    deq.append(a_ls[i])
                    check[a_ls[i]-1] = True
    if check.count(False) == 0:pass
    else:ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(' '))
path = [[False for i in range(N+1)] for j in range(N+1)]
connect_list = []
for i in range(M):
    a, b = map(int, input().split(' '))
    path[a][b] = True
    path[b][a] = True
    connect_list.append((a, b))
visit = []


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


ans = 0
for j in range(M):
    a, b = connect_list[j]
    path[a][b] = False
    path[b][a] = False
    visit = [False for i in range(N+1)]
    connect = True
    dfs(1)
    for i in range(1, N+1):
        if not visit[i]:
            connect = False
    if not connect:
        ans += 1
    path[a][b] = True
    path[b][a] = True
print(ans)

Submission status: Accepted

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


    def root(self, n):
        if self.num_list[n] == n:
            return n
        else:
            self.num_list[n] = self.root(self.num_list[n])
            return self.num_list[n]

    def merge(self, a, b):
        a_root = self.root(a)
        b_root = self.root(b)
        tmp = min(a_root, b_root)
        self.num_list[a_root] = tmp
        self.num_list[b_root] = tmp
        return


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

ans = 0
U = union_find(n)
for i in range(m):
    U.__init__(n)
    for j in range(m):
        if i == j:
            continue
        U.merge(edge[j][0]-1, edge[j][1]-1)
    setE = set()
    for k in range(n):
        setE.add(U.root(k))
    if len(setE) > 1:
        # print(setE)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().strip().split())
graph = [[False for _ in range(N)] for _ in range(N)]
visited = [False for _ in range(N)]
aa, bb = [], []
ans = 0
for _ in range(M):
  a, b = map(int, input().strip().split())
  aa.append(a)
  bb.append(b)
  graph[a-1][b-1] = graph[b-1][a-1] = True

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

for a, b in zip(aa, bb):
  graph[a-1][b-1] = graph[b-1][a-1] = False
  for _v in range(len(visited)):
    visited[_v] = False
  dfs(0)
  if all(v for v in visited):
    ans += 1
  graph[a-1][b-1] = graph[b-1][a-1] = True

print(M - ans)

Submission status: Accepted

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

def cal(AB):
    matrix = [[] for i in range(N)]
    for a, b in AB:
        matrix[a].append(b)
        matrix[b].append(a)
    check = [0] * N
    check[0] = 1
    deque = [0]
    while deque:
        now = deque.pop()
        for i in matrix[now]:
            if check[i] == 0:
                deque.append(i)
                check[i] = 1
    if len(set(check)) == 1:
        return 0
    else:
        return 1

for i in range(M):
    AB = ab[:]
    del AB[i]
    ans += cal(AB)

print(ans)

Submission status: Accepted

Solution code:
#2次元配列を表示
def print_arr2(arr):
    for i in range(len(arr)):
        for j in range(len(arr[i])):
            print(arr[i][j],end="")
        print()
    print()

import copy

def dfs(node,edge):
    ok = True
    narr = [0 for _ in range(node)]
    M = len(edge)
    stack = []
    stack.append([0,-1])
    narr[0] = 1
    while(stack != []):
        start = stack.pop(-1)
        for i in range(M):
            if edge[start[0]][i] == 1 and narr[i] != 1:
                narr[i] = 1
                stack.append([i,start[0]])
    for i in range(node):
        if narr[i] != 1:
            ok = False
    return ok
        
N,M = map(int,input().split())
edge = [[0]*N for _ in range(N)]
tedge = [[0]*N for _ in range(N)]
count = 0
for i in range(M):
    go, to = map(int,input().split())
    edge[go-1][to-1] = 1
    edge[to-1][go-1] = 1

for go in range(N):
    for to in range(go,N):
        if edge[go][to] == 1:
            tedge = copy.deepcopy(edge)
            tedge[go][to] = 0
            tedge[to][go] = 0
            if dfs(N,tedge) == False:
                count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_list = []
b_list = []

for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


count = 0
for j in range(m):
    items = [dict() for _ in range(n)]
    for i in range(m):
        a, b = a_list[i] - 1, b_list[i] - 1
        if i == j:
            continue
        items[a][b] = 1
        items[b][a] = 1
    di = Dijkstra(items, a_list[0] - 1).execute()
    if len([True for d in di[0] if d == float("inf")]) >= 1:
        count += 1
print(count)

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:
def is_tree(g, n):
    visiteds = [False] * n
    q = [0]
    while q:
        i = q.pop()
        if visiteds[i]:
            continue
        visiteds[i] = True
        for to in g[i]:
            if not visiteds[to]:
                q.append(to)
    return all(visiteds)


def main():
    global n
    n, m = map(int, input().split())
    g = [set() for _ in range(n)]
    es = []
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        g[a].add(b)
        g[b].add(a)
        es.append((a, b))

    res = 0
    for a, b in es:
        g[a].remove(b)
        g[b].remove(a)
        if not is_tree(g, n):
            res += 1
        g[a].add(b)
        g[b].add(a)

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = 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:
            self._size -= 1
            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)

    def size(self):
        return self._size

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())

ans = 0
for i in range(M):
    uf = UnionFind(n=N)
    for j in range(M):
        if j == i:
            continue
        uf.union(a[j]-1, b[j]-1)
    if uf.size() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self.sizes = [0] * n
        self.par = list(range(n))

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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


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
ans = 0
for i in range(M):
    uf = uf_tree(N+1)
    for j in range(M):
        if i == j:
            continue
        uf.unite(a[j], b[j])

    bridge = False
    for i in range(N):
        if not uf.same(0, i):
            bridge = True
    if bridge:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

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

for i in range(M):
	graph = defaultdict(list)
	for j in range(M):
		if j != i:
			a = mlist[j][0]
			b = mlist[j][1]
			graph[a - 1].append([b - 1, 1])
			graph[b - 1].append([a - 1, 1])
		dist_node = [float("inf") for i in range(N)]
		s = 0
		dist_node[s] = 0

		Q = []
		heapq.heappush(Q, (dist_node[s], s)) 

		while Q: 
			dis, v = heapq.heappop(Q)
			if dist_node[v] < dis:
				continue
			for u, w in graph[v]:
				alt = dis + w
				if dist_node[u] > alt:
					dist_node[u] = alt
					heapq.heappush(Q, (alt, u))
	if dist_node.count(float("inf")) != 0:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
N, M = map(int, input().split())
a, b = [0] * M, [0] * M
g = [[False] * N for _ in range(N)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    g[a[i]-1][b[i]-1] = True
    g[b[i]-1][a[i]-1] = True

ans = 0
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = False
    g[_b-1][_a-1] = False
    visit = [False] * N
    q = Queue()
    q.put(0)
    while not q.empty():
        v = q.get()
        visit[v] = True
        for adj_v, adj in enumerate(g[v]):
            if not adj or visit[adj_v]:
                continue
            q.put(adj_v)
    if not all(visit):
        ans += 1
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True
print(ans)

Submission status: Accepted

Solution code:
def dfs(v):
    visit[v] = True
    for adj_v in [v for v, adj in enumerate(g[v]) if adj and not visit[v]]:
        dfs(adj_v)

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())

g = [[False] * N for _ in range(N)]
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True

ans = 0
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = False
    g[_b-1][_a-1] = False
    visit = [False] * N
    dfs(0)
    if not all(visit):
        ans += 1
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True
print(ans)

Submission status: Accepted

Solution code:
from math import isinf

V,E = map(int, input().split())
a,b = [0]*E, [0]*E
for i in range(E):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for l in range(E):
    d = [[float('inf')]*V for _ in range(V)] # 各頂点間距離
    for i in range(V):
        d[i][i] = 0
    for i in range(E):
        if i==l: continue 
        d[a[i]][b[i]] = 1
        d[b[i]][a[i]] = 1
        
    # ワーシャルフロイド
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    bridge = False
    # print(a[l], b[l], d[0])
    for dd in d[0]:
        if isinf(dd): bridge=True
    if bridge:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    # par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
    def __init__(self, size:int):
        self.par = [-1]*size
        self.rank = [0]*size
        for i in range(size):
            self.par[i] = i
    
    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
        
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        
        # 短いほうを長いほうにくっつける
        if self.rank[root_x] < self.rank[root_y]:
            self.par[root_x] = root_y
        else:
            self.par[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
                

##### main #####
N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue # この辺はパス
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    """
    - sizeを指定
    - 要素をグループにまとめる(unite) 
    - 要素同士が同じグループか判定する(isSame)
    - 分離はできない
    - par: 親の番号(はじめ par[i]==i つまりすべての頂点が根)
     - 始め各要素は別々のグループ"""
    def __init__(self, size: int):
        self.par = [-1]*size
        for i in range(size):
            self.par[i] = i 
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def isSame(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y

        
        
##### main #####
N,M = map(int, input().split())
a,b = [0]*M, [0]*M
for i in range(M):
    ai,bi = map(int, input().split())
    a[i],b[i] = ai-1, bi-1
    
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i==j: continue # この辺はパス
        uf.unite(a[j], b[j])
    bridge = False
    for i in range(N):
        if not uf.isSame(0,i):
            bridge = True
    if bridge:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# C
N,M = map(int, input().split())
graph = [[False]*N for _ in range(N)]
visited = [False]*N

def dfs(cur):
    global visited
    visited[cur] = True
    for nxt in range(N):
        if graph[cur][nxt]==False: continue
        if visited[nxt]==True: continue
        dfs(nxt)


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

ans = 0
for i in range(M):
    graph[a[i]][b[i]] = False # 辺を消す
    graph[b[i]][a[i]] = False
    # print("graph: "+"\n".join(map(str, graph)))
    visited = [False]*N
    dfs(0)
    if not all(visited):
        ans += 1
    graph[a[i]][b[i]] = True # 辺を戻す
    graph[b[i]][a[i]] = True
    
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
edge = [[False for j in range(n)] for i in range(n)]
for i in range(m):
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = True
visited = [False for j in range(n)]

def dfs(v):
	visited[v] = True
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)

ans = 0
for i in range(m):
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = False
	for j in range(n):
		visited[j] = False
	dfs(0)
	bridge = False
	for j in range(n):
		if visited[j]==False:
			bridge = True
			break
	if bridge:
		ans += 1
	edge[ab[i][0]-1][ab[i][1]-1] = edge[ab[i][1]-1][ab[i][0]-1] = True
print(ans)

Submission status: Accepted

Solution code:
def bfs(n, path):
    check = [0]*n
    check[0] = 1
    que = [0]
    while que:
        u = que.pop()
        for v in path[u]:
            if check[v] == 0:
                check[v] = 1
                que.append(v)
    if check != [1]*n:
        return 1
    else:
        return 0

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

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

for i in range(m):
    edges = [[] for _ in range(n)]
    for j in range(m):
        if j != i:
            edges[A[j]] += [B[j]]
            edges[B[j]] += [A[j]]
    ans += bfs(n, edges)
print(ans)

Submission status: Accepted

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

G = [set() for _ in range(N)]
a = set()
for ab in AB:
    G[ab[0]].add(ab[1])


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if j in G[i]:
            Gn = copy.deepcopy(G)
            Gn[i].discard(j)
            a = [i for i in range(N)]
            for k in range(N - 1):
                for l in Gn[k]:
                    unite(a, k, l)
            par = set()
            for k in range(N):
                par.add(find(a, k))
            if len(par) > 1:
                ans += 1
print(ans)