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 = list(map(int, input().split()))


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


uf = UnionFind(n)
al = [0] * m
bl = [0] * m
for i in range(m):
    al[i], bl[i] = map(int, input().split())

ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        else:
            uf.union(al[j]-1, bl[j]-1)
    if uf.size(0) == n:
        continue
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

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

N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int, input().split())
ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if j!=i:
            uf.union(A[j]-1,B[j]-1)
    if len(uf.roots())>1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
N, M = map(int, input().split())
edge = []
for _ in range(M):
    edge.append(list(map(int, input().split())))
ans = 0 
for i in range(M):
    done = [True for _ in range(N + 1)]
    renketu = [[] for _ in range(N + 1)]
    for j in [k for k in range(M) if k != i]:
        a, b = edge[j][0], edge[j][1]
        renketu[a].append(b)
        renketu[b].append(a)
    q = deque([1])
    while q:
        now = q.pop()
        done[now] = False

        for r in renketu[now]:
            if done[r]:
                q.append(r)
    if sum(done) > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
        
import numpy as np
N, M = map(int, input().split())
edge = []
for _ in range(M):
    edge.append(list(map(int, input().split())))
ans = 0 
for i in range(M):
    unionfind = UnionFind(N)
    for j in [k for k in range(M) if k != i]:
        a, b = edge[j][0] - 1, edge[j][1] - 1
        unionfind.union(a, b)
    if np.count_nonzero(np.array(unionfind.parents) < 0) >= 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
cnt_dict = defaultdict(int)

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

ans = 0
while True:
    cnt = Counter(cnt_dict).most_common()
    if cnt[-1][1] > 1:
        break
    elif cnt[-1][1] == 1:
        ans += 1
        key = cnt[-1][0]
        cnt_dict[key] = float("inf")
        for i in range(1, N + 1):
            if key in set(edge[i]):
                cnt_dict[i] -= 1
                edge[i].remove(key)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[]
    for i in range(M):
        a,b=map(int1,input().split())
        edge.append((a,b))
    class UnionFind:
        def __init__(self,n):
            self.par=[i for i in range(n)]
            self.siz=[1]*n
            
        def root(self,x):
            while self.par[x]!=x:
                self.par[x]=self.par[self.par[x]]
                x=self.par[x]
            return x
        
        def unite(self,x,y):
            x=self.root(x)
            y=self.root(y)
            if x==y:
                return False
            if self.siz[x]<self.siz[y]:
                x,y=y,x
            self.siz[x]+=self.siz[y]
            self.par[y]=x
            return True
        
        def is_same(self,x,y):
            return self.root(x)==self.root(y)
        
        def size(self,x):
            return self.siz[self.root(x)]
    ans=0
    for i in range(M):
        u=UnionFind(N)
        for j in range(M):
            if i==j:
                continue
            u.unite(edge[j][0],edge[j][1])
        if u.size(0)<N:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

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

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

    # 要素xが属するグループに属する要素をリストで返す
    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()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def resolve():
    N, M = map(int, input().split())
    E = [[int(x) - 1 for x in input().split()] for _ in range(M)]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        # i番目の辺を除くすべての辺をつないぐ
        for j, e in enumerate(E):
            if i == j:
                continue
            uf.union(e[0], e[1])
        # i番目の辺を除くすべての辺をつないだあとで、i番目の辺(a, b)がつながるかを判定する
        # つながらないならば、そのi番目の辺は橋である
        a, b = E[i]
        if not uf.is_same(a, b):
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [{} for i in range(n+1)]
for i in range(m):
    u,v = inm()
    dst[u][v] = dst[v][u] = i
sm = 0
for i in range(m):
    q = [1]
    done = [False]*(n+1)
    done[0] = done[1] = True
    while len(q)>0:
        x = q.pop()
        for y in dst[x]:
            if done[y] or dst[x][y]==i:
                continue
            done[y] = True
            q.append(y)
    if len([x for x in done if not x])>0:
        sm += 1
print(sm)

Submission status: Accepted

Solution code:
from scipy.sparse import coo_matrix, csgraph
N, M = map(int, input().split())
points = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M))
matrix = coo_matrix(([1] * M, tuple(zip(*points))), shape=(N, N)).toarray()
total = 0
for point in points:
    matrix[point] = 0
    total += csgraph.connected_components(matrix, directed=False, return_labels=False) != 1
    matrix[point] = 1
print(total)

Submission status: Accepted

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(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):
    unionFind=UnionFind(n+1)
    for j,k in enumerate(AB):
        a,b=k
        if i==j:continue
        else:unionFind.Unite(a,b)
    ans +=0 if unionFind.size(1)==n else 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import deque
from heapq import heappush, heappop


def warshallfloyd(cost,V):
    INF = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k]!=INF and cost[k][j]!=INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

    for i in cost:
        if float("inf") in i:
            return False
    
    return True

N,M = map(int,input().split())
edge = [[float("inf") for i in range(N)] for j in range(N)]
ab = []
for _ in range(M):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
    edge[a-1][b-1] = 1
    edge[b-1][a-1] = 1

ans = 0

for a,b in ab:
    tmp = deepcopy(edge)
    tmp[a][b] = float("inf")
    tmp[b][a] = float("inf")
    if not warshallfloyd(tmp,N):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    def check(self, x, y):
        if self.find(x) == self.find(y):
            # print('x, yの親は',self.par[x], self.par[y])
            return True
        else:
            return False
    def find(self, x):
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

                
n, m = map(int, input().split())
uf = UnionFind(n)
ans = 0
G = []

for i in range(m):
    a, b = map(int, input().split())
    G.append((a-1, b-1))
# print()
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i==j:
            continue
        uf.union(G[j][0], G[j][1])
    # print(uf.par)
    if not uf.check(G[i][0], G[i][1]):
        # print(G[i][0]+1, G[i][1]+1)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def search(u, g, visited):
	if visited[u]:
		return
	visited[u] = True
	for v in g[u]:
		search(v, g, visited)

def resolve():
	n, m = map(int, input().split())
	edges = [list(map(int, input().split())) for _ in range(m)]
	ans = 0
	for i in range(m):
		g = [[] for _ in range(n)]
		for j in range(m):
			if i == j:
				continue
			a, b = edges[j]
			g[a-1].append(b-1)
			g[b-1].append(a-1)
		visited = [False]*n
		search(0, g, visited)
		if visited.count(True) != n:
			ans += 1
	print(ans)
resolve()

Submission status: Accepted

Solution code:
import networkx as nx

N, M = map(int, input().split())
G = nx.Graph()
G.add_edges_from([tuple(map(int, input().split())) for _ in range(M)])

print(len(tuple(nx.bridges(G))))

Submission status: Accepted

Solution code:
#Nはノード数、Mはエッジ数
n,m = map(int, input().split())

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

cnt=0

for x in ab:
  ls=list(range(n))
  for y in ab:
    if y !=x:
      for i in range(n):
        ls=[ls[y[0]-1] if ls[i]==ls[y[1]-1] else ls[i] for i in range(n)] #bの値を根っこ（低い方a）にする
  if len(set(ls)) !=1:
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    e = [set() for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x: int(x) - 1, input().split())
        e[u].add(v)
        e[v].add(u)

    ans = 0
    for _ in range(m):
        count = 0
        for i, x in enumerate(e):
            if len(x) == 1:
                j = x.pop()
                e[j] -= {i}
                count += 1
        if count:
            ans += count
        else:
            print(ans)
            exit()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *ab = map(int, open(0).read().split())
    e = [set() for _ in range(n)]
    for u, v in zip(*[iter(ab)] * 2):
        e[u - 1].add(v - 1)
        e[v - 1].add(u - 1)

    ans = 0
    for _ in range(m):
        count = 0
        for i, x in enumerate(e):
            if len(x) == 1:
                j = x.pop()
                e[j] -= {i}
                count += 1
        if count:
            ans += count
        else:
            print(ans)
            exit()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *ab = map(int, open(0).read().split())
    e = [[] for _ in range(n)]
    for u, v in zip(*[iter(ab)] * 2):
        e[u - 1].append(v - 1)
        e[v - 1].append(u - 1)

    ans = 0
    for _ in range(m):
        count = 0
        for i, x in enumerate(e):
            if len(x) == 1:
                e[i] = []
                e[x[0]].remove(i)
                count += 1
        if count:
            ans += count
        else:
            print(ans)
            exit()




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m, *ab = map(int, open(0).read().split())
    e = [[] for _ in range(n)]
    for u, v in zip(*[iter(ab)] * 2):
        e[u - 1].append(v - 1)
        e[v - 1].append(u - 1)

    ans = 0
    for _ in range(m):
        count = 0
        for i, x in enumerate(e):
            if len(x) == 1:
                e[i] = []
                e[x[0]].remove(i)
                count += 1
        if count:
            ans += count
        else:
            break

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy


def main():
    # n: 頂点数
    # w: 辺の数
    n, w = map(int, input().split())
    # v -> v ; cost: 0
    d = [[False] * n for i in range(n)]

    # d[u][v] : 辺u-vのコスト(if not: inf)
    e = []
    for i in range(w):
        # edge: u -> v ; cost : z
        u, v = map(lambda x: int(x) - 1, input().split())
        e.append([u, v])
        # 無向グラフを想定
        d[u][v] = True
        d[v][u] = True

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

    ans = 0
    for (u, v) in e:
        graph = copy.deepcopy(d)
        graph[u][v] = False
        graph[v][u] = False
        for i in range(n):
            visited = [False for _ in range(n)]
            dfs(graph, visited, i)
            if not all(visited):
                ans += 1
                break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys ; sys.setrecursionlimit(2000)
import copy

def dfs(v1):
    visited[v1] = 1
    for v2 in range(n):
        if graph[v1][v2] == 0: continue
        if visited[v2] == 1: continue
        dfs(v2)
# nは頂点の数
n, m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1,ab.T[1]-1

#隣接行列
G = np.array([[0] * n for _ in range(n)])
for aa,bb in zip(a,b): G[aa][bb],G[bb][aa] = 1,1

ans = 0
for aa,bb in zip(a,b):
    graph = copy.deepcopy(G)
    graph[aa][bb],graph[bb][aa] = 0,0
    visited = [0]*(n)
    dfs(0)
    if not all(visited): ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # https://www.slideshare.net/chokudai/union-find-49066733
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        # root[x]>=0の場合は、特に直接的な意味を持たない気がする。計算に寄与するので意味はあるのだろうが。
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        # 無結合の時はRank=0,結合して1つ木が深くなると根がRank+=1
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    #
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        # (1)xのランクの方が大きい(位置が深い)場合
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        # (2)yのランクの方が大きい(位置が深い)場合 or 等しい場合
        # また等しい場合、引数の2つめのyの方のランクを1つ増やす
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    # Return: True or False
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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

for i in range(M):
  UN=UnionFind(N)
  for j in range(M):
    if j==i:
      pass
    else:
      UN.Unite(a[j],b[j])
  if UN.isSameGroup(a[i], b[i])==False:
    cnt +=1
    
print(cnt)

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.parents = list(range(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:
            self.parents[y] = x


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

    ans = 0
    for i in range(M):
        # a[i], b[i] 以外を使ってUnionFind木を作り
        # グラフ全体が非連結になるなら橋
        uf = UnionFind(N)
        for j in range(M):
            if i != j:
                uf.union(a[j]-1, b[j]-1)

        p = uf.find(0)
        for k in range(1, N):
            if p != uf.find(k):
                ans += 1
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

#root = {}でいけるか

def find(a):
    if a==root[a]: return a
    else: root[a] = find(root[a]) ; return root[a]
    
def unite(a,b):
    ra,rb = find(a),find(b)
    if ra==rb : return
    else: root[ra] = rb
    
def same(a,b): return find(a)==find(b)

n,m =  map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0]-1, ab.T[1]-1

ans = 0
for i in range(m):
    root = list(range(n))
    connect = 0
    for j in range(m):
        if i==j: continue
        if not same(a[j],b[j]): unite(a[j],b[j]); connect += 1
    ans += 0 if connect==n-1 else 1
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def find(x):
    if x == root[x]: return x
    else: root[x] = find(root[x]); return root[x]
def unite(x,y):
    px,py = find(x),find(y)
    if px == py : return
    else: root[px] = py
def same(x,y): return find(x)==find(y)


n,m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0] -1, ab.T[1] -1

ans = 0
for i in range(m): #除外する辺を決める
    connect = 0
    root = list(range(n))
    for j in range(m): #i以外の辺についてuniteしていく
        if i != j and  not same(a[j],b[j]):
            unite(a[j],b[j]) ; connect += 1
    ans += 0 if connect == n-1 else 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

class unionfind: #ノード数nを読み込む
    def __init__(self,n): #コンストラクタ
        self.parent = list(range(n))
    def find(self,a): #根を探す、そのつど根を更新
        if self.parent[a] == a: return a #自分が根だったら終了
        else:
            self.parent[a] = self.find(self.parent[a]) #経路圧縮
            return self.parent[a]
    def unite(self,a,b): #ランク度外視で根を合体する
        pa,pb = self.find(a),self.find(b)
        if pa == pb: return 0 #根が一緒なら何もせず終了
        else: self.parent[pa] = pb
    def same(self,a,b):
        pa,pb = self.find(a),self.find(b)
        return pa == pb

# クラスを使わない実装
def find(x):
    if node[x] == x: return x
    else: node[x] = find(node[x]) ; return node[x]
def unite(x,y):
    x,y = find(x),find(y)
    if x == y : return
    else: node[x] = y
def same(x,y): return find(x) == find(y)


n,m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0] -1, ab.T[1] -1

ans = 0
for i in range(m): #除外する辺を決める
    connect = 0
    node = list(range(n))
    for j in range(m): #i以外の辺についてuniteしていく
        if i != j and  not same(a[j],b[j]): unite(a[j],b[j]) ; connect += 1
    ans += 0 if connect == n-1 else 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

class unionfind: #ノード数nを読み込む
    def __init__(self,n): #コンストラクタ
        self.parent = list(range(n))
    def find(self,a): #根を探す、そのつど根を更新
        if self.parent[a] == a: return a #自分が根だったら終了
        p = self.find(self.parent[a])
        self.parent[a] = p #根をダイレクトに更新
        return p
    def unite(self,a,b): #ランク度外視で根を合体する
        pa,pb = self.find(a),self.find(b)
        if pa == pb: return 0 #根が一緒なら何もせず終了
        self.parent[pa] = pb
    def same(self,a,b):
        pa,pb = self.find(a),self.find(b)
        return pa == pb

n,m = map(int,input().split())
ab = np.array([list(map(int,input().split())) for i in range(m)])
a,b = ab.T[0] -1, ab.T[1] -1

ans = 0
for i in range(m): #除外する辺を決める
    uf = unionfind(n)
    connect = 0
    for j in range(m): #i以外の辺についてuniteしていく
        if i != j and not uf.same(a[j],b[j]): uf.unite(a[j],b[j]) ; connect += 1
    ans += 0 if connect == n-1 else 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
import copy


class unionfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.groupnum = n

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return
        self.parent[pa] = pb
        # if(self.rank[pa] < self.rank[pb]):
        #     self.parent[pa] = pb
        # else:
        #     self.parent[pb] = pa
        #     if self.rank[pa] == self.rank[pb]:
        #         self.rank[pa] += 1
        self.groupnum -= 1

    def same(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        return pa == pb

    def find(self, a):
        if self.parent[a] == a:
            return a
        p = self.find(self.parent[a])
        self.parent[a] = p
        return p
    


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

    edge_list = []

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

    cnt = 0
    # 除外する辺ごとに。
    for i in range(m):
        uf = unionfind(n)
        for j in range(m):
            if i == j:
                continue
            uf.unite(edge_list[j][0], edge_list[j][1])
        if uf.groupnum >= 2:
            cnt += 1


    print(cnt)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
import copy


class unionfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]
        self.groupnum = n

    def unite(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa == pb:
            return
        if(self.rank[pa] < self.rank[pb]):
            self.parent[pa] = pb
        else:
            self.parent[pb] = pa
            if self.rank[pa] == self.rank[pb]:
                self.rank[pa] += 1
        self.groupnum -= 1

    def same(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        return pa == pb

    def find(self, a):
        if self.parent[a] == a:
            return a
        p = self.find(self.parent[a])
        self.parent[a] = p
        return p
    


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

    edge_list = []

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

    cnt = 0
    # 除外する辺ごとに。
    for i in range(m):
        uf = unionfind(n)
        for j in range(m):
            if i == j:
                continue
            uf.unite(edge_list[j][0], edge_list[j][1])
        if uf.groupnum >= 2:
            cnt += 1


    print(cnt)
    return 0

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')

n_nodes, m_edges = map(int, input().split())
edges = []
for _ in range(m_edges):
    u, v = map(int, input().split())
    edges.append([u - 1, v - 1])
# pprint(edges)


def find_root(v):
    if v != parents[v]:
        parents[v] = find_root(parents[v])
    return parents[v]


def has_same_root(u, v):
    return find_root(u) == find_root(v)


def unite(u, v):
    root_u, root_v = find_root(u), find_root(v)
    if root_u == root_v:
        return
    if rank[root_u] < rank[root_v]:
        root_u, root_v = root_v, root_u
    parents[root_v] = root_u
    rank[root_u] += rank[root_v]


res = 0
for i in range(m_edges):
    parents = [i for i in range(n_nodes)]
    rank = [1] * n_nodes
    for j in range(m_edges):
        if i == j:
            continue
        u, v = edges[j]
        if not has_same_root(u, v):
            unite(u, v)
    # pprint(parents)
    count = 0
    for v in range(n_nodes):
        if parents[v] == v:
            count += 1
    if count > 1:
        res += 1

print(res)