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:
from itertools import combinations

class unionfind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[1]*n

    def root(self,a):
        if self.par[a]==a : return a
        parent=self.root(self.par[a])
        self.par[a]=parent
        return parent

    def unite(self,a,b):
        ra,rb=self.root(a),self.root(b)
        if ra==rb : return
        if self.rank[ra]>self.rank[rb]:
            ra,rb=rb,ra
        self.par[rb]=ra
        self.rank[ra]+=1

    def same(self,a,b):
        return self.root(a)==self.root(b)


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

    sm=0
    for e_remove in edges:
        uf=unionfind(n)
        for e in edges:
            if e==e_remove : continue
            uf.unite(e[0]-1,e[1]-1)

        for a in combinations(range(n),2):
            if not uf.same(a[0],a[1]):
                break
        else : continue
        sm+=1

    print(sm)

main()

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())
  a, b = a-1, b-1
  graph[a].append(b)
  graph[b].append(a) 
    
def dfs(x,g):
    if vis[x]:return
    vis[x]=1
    for i in g[x]:
     dfs(i,g)
    return

ans=0
for i in range(len(graph)):
    for j in range(len(graph[i])):
        t=graph[i]
        gn=graph[0:i]+[t[0:j]+t[j+1:]]+graph[i+1:]
        vis=[0]*N
        dfs(0,gn)
        if not(all(vis)):
            # print(i+1, graph[i][j]+1,gn,vis)
            ans+=1
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
#1回１回UnionFind繋ぎ直す
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int,input().split())))

out=0
for k in range(M):
    Network = UnionFind(N)
    for i in range(M):
        if i!=k:
            a,b = ab[i][0], ab[i][1]
            Network.union(a-1,b-1)
    if Network.group_count() != 1:
        out+=1

print(out)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc075/submissions/15509548

n, m = map(int, input().split())
g = [[] for _ in range(n)]
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)

def lowlink(g, root=0):
    n = len(g)
    order = [n]*n
    low = [n]*n

    s = [root]
    cnt = 0
    par = [-1]*n
    seq = []
    while s:
        v = s.pop()
        if order[v] != n:
            continue
        order[v] = cnt
        seq.append(v)
        low[v] = cnt
        cnt += 1
        for u in g[v]:
            if order[u] < cnt:
                if par[v] != u:
                    low[v] = min(low[v], order[u])
                    continue
            else:
                par[u] = v
                s.append(u)
    child = [[] for _ in range(n)]
    for v in range(n):
        if par[v] != -1:
            child[par[v]].append(v)
    seq.reverse()
    for v in seq:
        for u in child[v]:
            low[v] = min(low[v], low[u])
    # bridge
    bridge = []
    for p in range(n):
        for c in child[p]:
            if order[p] < low[c]:
                bridge.append((p, c))

    # articulation points
    AP = []
    for v in range(n):
        if v == root:
            if len(child[v]) >= 2:
                AP.append(v)
        else:
            for c in child[v]:
                if order[v] <= low[c]:
                    AP.append(v)
                    break
    return AP, bridge

_, bridge = lowlink(g, 0)
print(len(bridge))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]
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)

def lowlink(g, root=0):
    n = len(g)
    order = [n]*n
    low = [n]*n

    s = [root]
    cnt = 1
    par = [-1]*n
    seq = []
    while s:
        v = s.pop()
        if order[v] != n:
            continue
        order[v] = cnt
        seq.append(v)
        low[v] = cnt
        cnt += 1
        for u in g[v]:
            if order[u] < cnt:
                if par[v] != u:
                    low[v] = min(low[v], order[u])
                    continue
            else:
                par[u] = v
                s.append(u)
    child = [[] for _ in range(n)]
    for v in range(n):
        if par[v] != -1:
            child[par[v]].append(v)
    seq.reverse()
    for v in seq:
        for u in child[v]:
            low[v] = min(low[v], low[u])
    # bridge
    bridge = []
    for p in range(n):
        for c in child[p]:
            if order[p] < low[c]:
                bridge.append((p, c))

    # articulation points
    AP = []
    for v in range(n):
        if v == root:
            if len(child[v]) >= 2:
                AP.append(v)
        else:
            for c in child[v]:
                if order[v] <= low[c]:
                    AP.append(v)
                    break
    return AP, bridge

_, bridge = lowlink(g, 0)
print(len(bridge))

Submission status: Accepted

Solution code:
import itertools
#入力
N,M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

#橋はMAX50本なので、1本ずつ取り除いて全てが繋がるかどうかを試行する。

#UnionFind木


def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

#橋の組み合わせ
loop_list = list(itertools.combinations(ABs, M-1))
#print(loop_list)

ans = 0
for loop in loop_list:
    #ループ毎にリセットするので。良くない気がする。
    par = [i for i in range(N+1)]
    size = [1 for _ in range(N+1)]

    for bridge in loop:
        unite(bridge[0], bridge[1])
    
#    print(par)
#    print(size)
    if(max(size) != N):
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ans = 0
for i in range(m):
    UF = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        UF.union(ab[j][0] - 1, ab[j][1] - 1)
    if UF.size(0) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
N,M=map(int,input().split())
path_matrix=[[0 for i in range(N)] for j in range(N)]
L=[[] for i in range(M)]

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

color_white=["W" for i in range(N)]
color_black=["B" for i in range(N)]
visited=copy.deepcopy(color_white)

def path(x,y):
    path_matrix[x-1][y-1]=0
    path_matrix[y-1][x-1]=0
    return DFS(x,path_matrix)

def DFS(x,tim):
    visited[x-1]="B"
    if visited==color_black:
        return True
    total_ans=0
    for i in range(N):
        if tim[x-1][i]==1 and visited[i]=="W":
            total_ans=int(DFS(i+1,tim))

    return total_ans
    
ans=0
for i in range(M):
    visited=copy.deepcopy(color_white)
    if path(L[i][0],L[i][1])==0:
        ans+=1
    path_matrix[L[i][0]-1][L[i][1]-1]=1
    path_matrix[L[i][1]-1][L[i][0]-1]=1

print(ans)

Submission status: Accepted

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

edge = []
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    edge.append((a, b))
    graph[a].append(b); graph[b].append(a)

def dfs(now):
    searched[now] = True
    for next in graph[now]:
        if searched[next]:
            continue
        if min(now, next) == a and max(now, next) == b:
            continue
        dfs(next)

ans = M
for i in range(M):
    a, b = edge[i]
    searched = [False] * N
    dfs(0)
    if sum(searched) == N:
        ans -= 1

print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

out = 0
for broken in range(M):
    Network = UnionFind(N)
    for j in range(M):
        if j!=broken:
            A,B=AB[j][0],AB[j][1]
            Network.union(A-1, B-1)
    if Network.group_count()==2:
        out+=1
print(out)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.parents = [-1]*n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        

N,M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
ans = 0
for i in range(M):
    if i == M-1:
        ab = AB[:M-1]
    else:
        ab = AB[:i]+AB[i+1:]
    uf = UnionFind(N)
    for j in ab:
        uf.union(j[0]-1,j[1]-1)
    if uf.parents[uf.find(0)] != - N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if self.parents[x] == 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.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
num=[list(map(int,input().split())) for _ in range(m)]
ans=0
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if i!=j:
            uf.union(num[j][0]-1,num[j][1]-1)
    if uf.size[uf.find(0)]!=n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

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

# full search
# DFS
ans = 0
for i in range(m):
    seen = [True] * n
    todo = []
    start = a[i]
    goal = b[i]
    seen[start] = False
    for j in edge[start]:
        if j == goal:
            continue
        else:
            todo.append(j)
            seen[j] = False

    while len(todo) > 0 and seen[goal]:
        j = todo.pop(-1)
        for k in edge[j]:
            if seen[k]:
                todo.append(k)
                seen[k] = False

    if seen[goal]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

G = defaultdict(list)

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

# print(f'{G=}')


def f(a, b):
    S = set([])
    Q = [1]
    while True:
        QQ = []
        for q in Q:
            S.add(q)
            for j in G[q]:
                if q == a and j == b:
                    continue
                if q == b and j == a:
                    continue
                if j not in S:
                    QQ.append(j)
        if len(QQ) == 0:
            break
        Q = QQ
        # print(f'{QQ=}')
    # print(f'{a=}, {b=}, {S=}')
    return 1 if len(S) != N else 0


cnt = 0
for a, b in AB:
    cnt += f(a, b)

# print(f'{cnt=}')
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8

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

class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def union(self, x, y):
        x_root = self.root(x)
        y_root = self.root(y)
        if x_root == y_root:
            pass
        else:
            self.parent[x_root] = y_root

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

ans = 0

input_ = []
for _ in range(m):
    a, b = list(map(int, input().split(" ")))
    a -= 1
    b -= 1
    input_.append((a, b))

for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        a, b = input_[j]
        uf.union(a, b)
    for k in range(1, n):
        if not uf.same(0, k):
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
class UnionFindWithSize:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def sizeofset(self, x):
        return self.size[self.find(x)]
if __name__ == "__main__":
    N,M = map(int,input().split())
    edges = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
    ans = 0
    for i in range(M):
        uf = UnionFindWithSize(N)
        for j in range(M):
            if j != i:
                a,b = edges[j]
                uf.unite(a,b)
        if uf.sizeofset(0) != N:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
  
def bfs(l, tmp, came):
  t = []
  for n in tmp:
    for s in l:
      if (s[0]==n) and (s[1] not in came):
        t.append(s[1])
        came.append(s[1])
      elif (s[1]==n) and (s[0] not in came):
        t.append(s[0])
        came.append(s[0])
  if t == []:
    came = set(came)
    return came
  else:
    return bfs(l, t, came)
  
ans = 0
for i in range(M):
  x = copy.copy(l)
  x.pop(i)
  a = bfs(x, [1], [1])
  if len(a) < N:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.parents=[-1]*n
  
  def find(self,x):
    if self.parents[x]<0:
      return x
    self.parents[x]=self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    
    self.parents[x]+=self.parents[y]
    self.parents[y]=x

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

for _ in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
  
for i in range(M):
  uf=UnionFind(N+1)
  for j in range(M):
    if i==j:
      continue
    uf.union(A[j],B[j])
  else:
    if abs(min(uf.parents[1:]))!=N:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy
from collections import deque
N,M = map(int,input().split())
lsside = [[] for i in range(N+1)]
lsline = []
for i in range(M):
    a,b = map(int,input().split())
    lsside[a].append(b)
    lsside[b].append(a)
    lsline.append([a,b])

ans = 0
lsloop = []
for i in range(M):
    graph = copy.deepcopy(lsside)
    a = lsline[i][0]
    b = lsline[i][1]
    graph[a].remove(b)
    graph[b].remove(a)
    used = [False for i in range(N+1)]
    ii = 1
    d = deque()
    d.append(a)
    used[a] = True
    while d:
        v = d.popleft()
        for i in graph[v]:
            if used[i]:
                continue
            ii += 1
            d.append(i)
            used[i] = True
    lsloop.append(ii)
ans = M - lsloop.count(N)
print(ans)

Submission status: Accepted

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

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

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

N,M=list(map(int,input().split()))
S=set()
for _ in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    S.add((a,b))

ct=0
for i in S:
    T=S-{i}
    uf=UnionFind(N)
    for (j,k) in T:
        uf.union(j,k)
    a=uf.find(0)
    for l in range(1,N):
        if a!=uf.find(l):
            ct+=1
            break
print(ct)

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin
input = stdin.readline

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*n
    
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parent[x] < self.parent[y]:
            x,y = y,x
        
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        

N,M = map(int, input().split())
A = [-1]*M; B = [-1]*M
for i in range(M):
    a,b = map(lambda x: int(x) - 1, input().split())
    A[i] = a; B[i] = b

ans = 0
for exclude_idx in range(M):
    uf = Unionfind(N)
    for i in range(M):
        if i == exclude_idx:
            continue
        uf.union(A[i],B[i])
    
    cnt = 0
    for parent in uf.parent:
        if parent < 0:
            cnt += 1
    if cnt >= 2:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(current):
    for maps in Graph[current]:
        if maps in already:
            continue
        else:
            already.append(maps)
            dfs(maps)

n,m = map(int,input().split())
ans = 0
Edges = []
for _ in range(m):
    Edges.append([int(j)-1 for j in input().split()])

for i in range(m):
    egdes = Edges[0:i]+Edges[i+1:]
    Graph = [[] for _ in range(n)]
    for edge in egdes:
        Graph[edge[0]].append(edge[1])
        Graph[edge[1]].append(edge[0])
    already = []
    dfs(0)
    if len(already) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def root(i):
    if par[i] < 0:
        return i
    else:
        return root(par[i])

def size(a):
    return -par[root(a)]

def union(a,b):
    a = root(a)
    b = root(b)
    if a == b:#親が等しい
        return False
    if size(a) < size(b):#サイズが大きい方に繋げる
        a,b = b,a
    par[a] += par[b]
    par[b] = a
    return True

n,m = map(int,input().split())
bridge = []
for i in range(m):
    bridge.append([int(j)-1 for j in input().split()])
ans = 0
for i in range(m):
    par = [-1 for _ in range(n)]
    for j in range(m):
        if j != i:
            union(bridge[j][0],bridge[j][1])
    cnt = [ i for i in par if i < 0]
    if len(cnt) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())


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

    for i in range(m):
        uf = UnionFind(n)
        for j in range(m):
            if i == j:
                continue
            uf.merge(ab_list[j][0] - 1, ab_list[j][1] - 1)
        if uf.group_count() != 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin
input = stdin.readline

N,M = map(int, input().split())
neighbor = [[] for _ in range(N)]
A = [-1]*M; B = [-1]*M
for i in range(M):
    a,b = map(lambda x: int(x) - 1, input().split())
    A[i] = a; B[i] = b
    neighbor[a].append(b)
    neighbor[b].append(a)

cnt = 0
for i in range(M):
    a,b = A[i],B[i]
    neighbor[a].remove(b)
    neighbor[b].remove(a)
    visited = [False]*N
    queue = deque()
    queue.append(0)
    visited[0] = True
    
    while queue:
        x = queue.popleft()
        
        for z in neighbor[x]:
            if not visited[z]:
                visited[z] = True
                queue.append(z)
    
    
    if False in visited:
        cnt += 1
    
    neighbor[a].append(b)
    neighbor[b].append(a)

print(cnt)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
ab_list = []
ans =0
for i in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    ab_list.append([a, b])

for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        uf.union(ab_list[j][0], ab_list[j][1])
    if not uf.same(ab_list[i][0], ab_list[i][1]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数nで初期化"""
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ノードxが属するグループの根を返す"""
        if self.parents[x] < 0:
            return x
        else:
            #経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """xが属するグループとyが属するグループを併合"""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """xが属するグループの要素数を返す"""
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """x, yが同じグループに属するかどうかを返す"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """xが属するグループ内の要素をリストで返す"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """全ての根に対する要素をリストで返す"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """グループの総数を返す"""
        return len(self.roots())

    def all_group_members(self):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    
N, M = map(int, input().split())
from collections import defaultdict
E = []
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    E.append((a, b))

ans = 0
for bri in range(M):
    uf = UnionFind(N)
    for e in range(M):
        if e == bri:
            continue
        uf.union(*E[e])

    if uf.group_count() != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par = [i for i in range(n+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
ls = [list(map(int,input().split())) for _ in range(m)]
ans = 0
for i in ls:
    for k in ls:
        if i != k:
            [a,b] = k
            unite(a,b)
    flag = True
    for p in range(1,n+1):
        for q in range(1,n+1):
            if not same(p,q):
                flag = False
                break
        if flag == False:
            break
    if flag == False:
        ans += 1
    par = [i for i in range(n+1)]
print(ans)