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:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

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


# ある辺iを除いた残りの辺にそれぞれに対してuniteの操作を行ったのち、異なるparentsの数を数える
# 連結グラフであれば、異なるparentsの数は1になる
# 非連結グラフであれば、異なるparentsの数は2以上になる


def root(v):
    if parents[v] == v:
        return v
    parents[v] = root(parents[v])
    return parents[v]


def unite(u, v):
    u_root = root(u)
    v_root = root(v)
    if u_root == v_root:
        return
    parents[u_root] = v_root


def same(u, v):
    return root(u) == root(v)


ans = 0
for e_i in edges:
    parents = [i for i in range(N)]
    for e_j in edges:
        if e_i == e_j:
            continue
        u, v = e_j
        if not same(u, v):
            unite(u, v)
    count = 0
    for v in range(N):
        if parents[v] == v:
            count += 1
    if count > 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    # return: articulation points, bridges
    # The graph must be connected.
    def lowlink(adj, root=1):
        N = len(adj) - 1
        order = [N + 1] * (N + 1)
        low = [N + 1] * (N + 1)
        AP = []
        bridge = []

        st = [root]
        cnt = 1
        par = [0] * (N + 1)
        seq = []
        while st:
            v = st.pop()
            if order[v] != N+1:
                continue
            order[v] = cnt
            seq.append(v)
            low[v] = cnt
            cnt += 1
            for u in adj[v]:
                if order[u] < cnt:
                    if par[v] != u:
                        low[v] = min(low[v], order[u])
                        continue
                else:
                    par[u] = v
                    st.append(u)

        child = [[] for _ in range(N + 1)]
        for v in range(1, N + 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
        for p in range(1, N+1):
            for c in child[p]:
                if order[p] < low[c]:
                    bridge.append((p, c))

        # articulation point
        for v in range(1, N + 1):
            if v == root:
                if len(child[v]) > 1:
                    AP.append(v)
            else:
                for c in child[v]:
                    if order[v] <= low[c]:
                        AP.append(v)
                        break

        return AP, bridge

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

    AP, bridge = lowlink(adj)
    print(len(bridge))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# abc075_c.py

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+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を見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        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が同じグループに属するか判断
    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())
glaph = []
for i in range(M):
    A, B = map(int,input().split())
    glaph.append((A,B))

cnt = 0
for i in range(M):
    unionfind = UnionFind(N)
    for j,v in enumerate(glaph):
        x,y = v
        if i==j:
            continue
        unionfind.Unite(x,y)
    if unionfind.Count(1) < N:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,m=map(int,input().split())
  g=[[] for _ in range(n)]
  for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1;
    g[a].append((b,i))
    g[b].append((a,i))
  
  bfs=deque([])
  def check(j):
    res=1
    used=[False]*n
    used[0]=True
    bfs.append(0)
    while bfs:
      cur=bfs.popleft()
      for to,num in g[cur]:
        if num!=j and not used[to]:
          used[to]=True
          res+=1
          bfs.append(to)
    return res!=n
  
  ans=0
  for i in range(m):
    if check(i):
      ans+=1
  
  print(ans)
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c?lang=ja


def root(a):
    if parent[a] == -1:
        return a
    parent[a] = root(parent[a])
    return parent[a]


def unite(x, y):
    if same(x, y):
        return False

    x = root(x)
    y = root(y)
    parent[x] = y
    return True


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


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

result = 0
for i in range(m):
    parent = [-1 for _ in range(n)]
    for j in range(m):
        if j == i:
            continue
        a, b = edge[j]
        unite(a, b)
    a, b = edge[i]
    if not same(a, b):
        result += 1

print(result)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
AB = []
from collections import deque

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


out = 0
for remove in range(M):
    G = [[] for i in range(N)]
    for i in range(M):
        if i==remove:
            continue
        else:
            A,B=AB[i]
            G[A-1].append(B-1)
            G[B-1].append(A-1)
    s = 0
    visit = [0]*N
    que = deque([s])
    visit[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            if visit[w] == 1:
                continue
            visit[w] =  1
            que.append(w)
    if sum(visit)!=N:
        out+=1
print(out)

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(lambda x: int(x)-1, input().split())) for _ in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        a, b = AB[j][0], AB[j][1]
        if i == j:
            continue
        uf.union(a, b)
    if uf.group_count() > 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def dfs(f):
    if vis[f] == 1:
        return
    vis[f] = 1 #fを訪問済にする
    for t in v[f]: #fとつながっている頂点を読み込む
        if f != a or t != b: #(a,b)の組み合わせでなければ繰り返す
            dfs(t)

n, m = map(int, input().split())
v = [[] for i in range(n)]
e = []

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

ans = 0

for a, b in e:
    vis = [0]*n
    dfs(a)
    if vis[b] == 0: #aからa-bの辺以外を辿ってbに行けるなら1になる
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc075/tasks/abc075_c

from collections import defaultdict

N, M = map(int, input().split())
par = [-1] * N
G = defaultdict(list)

########################################
class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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

edges = []
ufG = UnionFind(N)
for _ in range(M):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    edges.append((ai, bi))
    G[ai].append(bi)
    G[bi].append(ai)
    ufG.unite(ai, bi)

# 1本以外を入れたグラフを考える
count = 0
for m in range(M):
    ufGm = UnionFind(N)
    for k in range(M):
        if k == m:
            continue
        ai, bi = edges[k]
        ufGm.unite(ai, bi)

    flag = False
    for k in range(N):
        if ufGm.size(k) != ufG.size(k):
            flag = True
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

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

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        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のそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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の属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        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):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         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())
 


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

    bridge = 0
    for i in range(M):
        tree = UnionFind(N)
        for j in range(M):
            if j == i: continue
            tree.union(edge[j][0], edge[j][1])
        if tree.group_count() != 1:
            bridge += 1
    print(bridge)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
adj = [[0]*(n+1) for i in range(n+1)]
edges = []
for i in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))
    adj[a][b] = 1
    adj[b][a] = 1


visited = [False] * (n+1)
parents = [None] * (n+1)
cycles = set()
count = 0
def dfs(u):
    for v in range(n+1):
        if adj[u][v]:
            if parents[u] == v:
                continue
            #print (u, v)
            #print (parents)
            adj[u][v], adj[v][u] = 0, 0
            if parents[v] is not None:
                #print ("Isn't None", u, v, parents[u])
                cycles.add(u)
                cycles.add(v)
                w = parents[u]
                while w != v:
                    cycles.add(w)
                    w = parents[w]
                
            if parents[v] == None: 
                parents[v] = u
                dfs(v)
parents[1] = 0
dfs(1)
ans = m
#print (parents)
for i in range(m):
    a, b = edges[i]
    if a in cycles and b in cycles:
        ans -= 1
print (ans)

Submission status: Accepted

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

visit=[0 for i in range(n)]
side=[[False for i in range(n)] for j in range(n)]

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

def bfs(x,y):
    que=[0]
    visit=[0 for i in range(n)]
    done=[[0 for i in range(n)] for j in range(n)]
    visit[0]=1
    while(que):
        now=que.pop(0)
    
        for i in l[now]:
            if ((now==x and i==y) or (now==y and i==x)) or (done[now][i]==True or done[i][now]==True):
                continue
            else:
                que.append(i)
                done[now][i]=True
                visit[now]+=1
                visit[i]+=1

    flag=0

    for i in visit:
        if i!=0:
            continue                  
        else:
            flag=1
            break

    if flag==1:
        return 1
    else:
        return 0

ans=0
for i in range(n):
    for j in range(i+1,n):
        if side[i][j]==True:
            ans+=bfs(i,j)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0
for i, j in e:
    used = {}
    q = deque([0])
    while q:
        u = q.popleft()
        for v in g[u]:
            if (v in used) or (i == u and j == v) or (i == v and j == u):
                continue
            else:
                q.append(v)
                used[v] = True
    if len(used) < N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#dfs(bfsと同じ)

from collections import deque

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

#dfs(基準)
#隣接リスト
G=[[] for _ in range(n)]
for i in range(m):
    a,b=edge[i]
    G[a].append(b)
    G[b].append(a)

base=0
dist=[0]*n
for i in range(n):
    if dist[i]==0:
        base+=1
        #dfs
        dist[i]=1
        s=deque()
        s.append(i)
        while s:
            now=s.pop()
            for next in G[now]:
                if dist[next]>0:
                    continue
                s.append(next)
                dist[next]=1


ans=0

for i in range(m):
    #隣接リスト
    G=[[] for _ in range(n)]
    for j in range(m):
        if j!=i:
            a,b=edge[j]
            G[a].append(b)
            G[b].append(a)
    
    #dfs
    temp=0
    dist=[0]*n
    for j in range(n):
        #print(i,j,temp,dist,G)
        if dist[j]==0:
            temp+=1
            #dfs
            dist[j]=1
            s=deque()
            s.append(j)
            while s:
                now=s.pop()
                for next in G[now]:
                    if dist[next]>0:
                        continue
                    s.append(next)
                    dist[next]=1
    if temp>base:
        ans+=1

print(ans)


#0-1
#| |
#2--

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())
edge=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge.append((a,b))

#基準
uf=UnionFind(n)
for i in range(m):
    uf.union(edge[i][0],edge[i][1])
groups=uf.group_count()

ans=0

#全探索
for i in range(m):
    uf=UnionFind(n)
    for j in range(m):
        if j!=i:
            uf.union(edge[j][0],edge[j][1])
    if uf.group_count()>groups:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = deque()
    q.append(1)
    seen = {1}
    while q:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
eg = [[] for _ in range(n + 1)]

al = [0] * m
bl = [0] * m

for i in range(m):
    a, b = map(int, input().split())
    eg[a].append(b)
    eg[b].append(a)
    al[i], bl[i] = a, b

ans = 0
for i in range(m):
    x, y = al[i], bl[i]
    q = [1]
    seen = {1}
    while len(q) > 0:
        v = q.pop()
        for t in eg[v]:
            if t in seen:
                continue
            elif (v == x and t == y) or (v == y and t == x):
                continue
            q.append(t)
            seen.add(t)
    if len(seen) != n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
from itertools import product
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

class Graph:
    #グラフを表す

    # 頂点につけるlabelの初期値（ラベリングされていないことを示す値）
    no_labeling_num = -1

    class Vertex:
        # 頂点を表す

        def __init__(self, g, no, label):
            """

            :param g: グラフを表す。またVertexを所有するオブジェクトでもある
            :param no: 頂点にグラフのなかで一意に割り振られた識別用の番号
            :param label: 探索された順番を表す番号。ラベル。
            """
            self.no = no
            self.g = g
            self.label = label

        def __str__(self):
            """
            　
            """
            return "no:{0},label:{1}".format(self.no,self.label)

        def adjacentVs(self):
            """ selfと隣接している頂点のリストを返す

            :return:
            """
            result = []
            for c in range(self.g.order):
                if self.g.aDJM[self.no][c] == 1:
                    result.append((self.g.vs[c]))
            return result

        def back_to_previous(self):
            """ 前に探索した頂点を返す（厳密な表現ではない）
            詳細
            ・この頂点に隣接する頂点において、ラベル付けされていない（未探索）なものがないときに、
            次に探索する頂点を返す関数
            ・自身のラベル番号より小さい頂点の中で一番近いものを返す
            ・存在しないときは「None」を返す

            :return:
            """
            result = None
            vs = list(filter(lambda x: self.label > x.label, self.adjacentVs()))
            if vs != []:
                result = vs[0]
                key0 = self.label - result.label
                for v in vs:
                    key1 = self.label - v.label
                    if (key1 < key0):
                        key0 = key1
                        result = v

            return result

    def __init__(self, aDJM):
        """
        
        :param aDJM:隣接行列
        """
        self.aDJM = aDJM
        self.order = len(aDJM)
        self.vs = [Graph.Vertex(self, i, self.no_labeling_num) for i in range(self.order)]

    def no_labelingVs(self, vs):
        """ 渡された頂点リストにおいてlabelingされていない頂点のリストを返す

        :return:
        """
        result = []
        for v in vs:
            if v.label == self.no_labeling_num:
                result.append(v)
        return result

    def isconnected(self):
        """ このグラフが連結グラフであるかどうかを判定する
        
        :return:
        """
        label = 0
        v = self.vs[0]
        v.label = label
        # 最初に探索した頂点が孤立点である場合に対処するための条件
        if v.adjacentVs()==[]:
            v=None
        else:
            v = v.adjacentVs()[0]
            label += 1
            v.label = label
        while (v != None):  # 現在探索中の頂点のラベルが0かつその点に隣接する頂点すべてが探索ずみだったら終了するようにする
            vs = self.no_labelingVs(v.adjacentVs())
            if vs == []:
                v = v.back_to_previous()
            else:
                v = vs[0]
                label += 1
                v.label = label

        return not(self.no_labeling_num in list(map(lambda x:x.label,self.vs)))


def main():
    N, M = mi()
    aDJM = [[0]*N for i in range(N)]
    a, b = i2(M)
    cnt = 0

    for i in range(M):
        aDJM[a[i]-1][b[i]-1] = 1
        aDJM[b[i]-1][a[i]-1] = 1
    
    for i in range(M):
        aDJM[a[i]-1][b[i]-1] = 0
        aDJM[b[i]-1][a[i]-1] = 0
        if not Graph(aDJM).isconnected():
            cnt += 1
        aDJM[a[i]-1][b[i]-1] = 1
        aDJM[b[i]-1][a[i]-1] = 1

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numpy import *
from scipy.sparse.csgraph import *
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G1 = zeros((N,N))
ans = 0

for a,b in E:
  G1[a-1][b-1]+=1
  G1[b-1][a-1]+=1

for a,b in E:
  G2 = G1.copy()
  G2[a-1][b-1]-=1
  G2[b-1][a-1]-=1
  D = floyd_warshall(G2)
  if inf in D:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
L =[list(map(int, input().split())) for _ in range(m)]
#print(L)
cnt = 0
for i in range(m):
    G = [[] for _ in range(n)]
    
    for j in range(m):
        if i == j:
            continue
        a,b = L[j][0],L[j][1]
        #print(a-1,b-1)
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    #print(G)
    Q = deque()
    Q.append(0)
    visited = [0]*n
    visited[0] = 1
    while Q:
        q = Q.pop()
        for g in G[q]:
            if visited[g] == 0:
                visited[g] = 1
                #print(visited)
                Q.append(g)

    if 0 in visited:
        cnt +=1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
g = [[] for i in range(n)]
ab = []
for k in range(m):
  i,j = map(int,input().split())
  i,j = i-1,j-1
  g[i].append(j)
  g[j].append(i)
  ab.append((i,j))
c = 0
for i in range(m):
  visited = [1]+[0]*(n-1)
  stack = [0]
  while stack:
    cur = stack.pop()
    for j in g[cur]:
      if ab[i] in [(cur,j),(j,cur)]:
        continue
      if visited[j] == 0:
        visited[j] = 1
        stack.append(j)
  if 0 in visited:
    c += 1
print(c)

Submission status: Accepted

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

con = [[0]*(N+1) for _ in range(N+1)]
edge = []
for i in range(M):
    a, b = map(int, input().split())
    con[a][b] = con[b][a] = 1
    edge.append((a, b))

def floodfill(listz, comp):
    cnt = 0
    #print('comp = {}'.format(comp))
    while len(listz):
        newlistz = []
        for node in listz:
            compo[node] = comp
            cnt += 1
            #print(node)
            for i in range(1, N+1):
                if visited[i] == 0 and con[node][i] > 0:
                    visited[i] = 1
                    newlistz.append(i)
        listz = newlistz

    return cnt

ans = 0

for kk in range(M):
    a, b = edge[kk]
    con[a][b] = con[b][a] = 0
    #print('cut edge{} {}'.format(a, b))
    visited = [0] * (N + 1)
    compo = [0] * (N + 1)
    compID = 0
    total = 0
    for i in range(1, N+1):
        if visited[i] == 0:
            visited[i] = 1
            count = floodfill([i], compID)
            if count > 0:
                compID += 1
                total += count
                if total >= N:
                    break

    if compID > 1:
        ans += 1
    #return
    con[a][b] = con[b][a] = 1


print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = []
edges = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    l.append([a - 1, b - 1])
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
def dfs(cur, a, b):
    if visited[cur] == 1:
        return None
    visited[cur] = 1
    for v in edges[cur]:
        if v != b or cur != a:
            dfs(v, a, b)
ans = 0
for i in l:
    i, j = i[0], i[1]
    visited = [0 for i in range(n)]
    dfs(i, i, j)
    if visited[j] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
#辺を取り除くことはabのセットとなっている要素から取り除くことと等価。頂点を消すのではない。
ab = [list(map(int, input().split())) for _ in range(M)]
c = 0
for i in range(M):
    G = [[] for _ in range(N)]
    for j in range(M):
        if i == j:
            continue
        a, b = ab[j][0], ab[j][1]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)
    Q = deque()
    Q.append(0)
    d = [0] * N
    d[0] = 1
    while Q:
        q = Q.popleft()
        for g in G[q]:
            if d[g] == 0:
                d[g] = 1
                Q.append(g)
    if 0 in d:
        c += 1

print(c)

Submission status: Accepted

Solution code:
import sys
from collections import deque
 
N, M = list(map(int,input().split()))
AB = [ list(map(int,input().split())) for _ in range(M)] #Nは頂点、Mは辺数、ABはつながっている部屋
 


count = 0
for sub in range(M):
    graph = [[] for _ in range(N + 1)] #本来は頂点数さえあればいいけど、添え字処理の都合でN+1個
    for i in range(len(AB)): #つながっている頂点セット
        if i == sub:
            continue
        else:
            graph[AB[i][0]].append(AB[i][1])
            graph[AB[i][1]].append(AB[i][0]) #有行グラフだとこの行はなくていい
     
    # bfs
    queue = deque([1]) #queue = 訪れるリスト 今回は1からスタート固定だけど、出発点がいろいろある場合はループ
    signposts = [0] * (N + 1) #これはこの問題特有。
    visit = []
    while queue: #訪れるリストがあるうちは繰り返す
        u = queue.popleft() #先入れ先出し、つまり幅優先。popにすれば深さ優先
        visit.append(u)
        for v in graph[u]: #頂点uにある隣接頂点をチェック
            if (v not in visit) and (v not in queue): #この問題特融だが、おとずれたチェックとしてvisitリストが必裕　おとずれていなかったらこの分岐に入る
                queue.append(v) #訪れるリストに頂点を追加

    if len(visit)!= N:
        count +=1
print(count)