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 collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
move = [(0, 1), (1, 1), (-1, 1), (0, -1), (1, -1), (-1, -1), (1, 0), (-1, 0)]
#A
def A():
    a, b, c = LI()
    if a == b:
        print(c)
    if b == c:
        print(a)
    if a == c:
        print(b)
    return

#B
def B():
    h, w = LI()
    s = SR(h)
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                b = 0
                for my, mx in move:
                    ym = my + y
                    xm = mx + x
                    if 0 <= ym < h and 0 <= xm < w:
                        if s[ym][xm] == "#":
                            b += 1
                s[y][x] = b
    for i in range(h):
        print("".join(map(str, s[i])))
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    ab = LIR_(m)
    for a,b in ab:
        edg[a].append(b)
        edg[b].append(a)
    ans = 0
    for a, b in ab:
        c = [True] * n
        ed = defaultdict(int)
        q = deque()
        q.append(0)
        c[0] = False
        ed[(a,b)] = True
        while q:
            now = q.pop()
            for e in edg[now]:
                if ed[(now,e)] or ed[(e,now)]:
                    continue
                ed[(now, e)] = True
                c[e] = False
                q.appendleft(e)
        if True in c:
            ans += 1
    print(ans)
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
ans = 0
for x in edges:
    l = list(range(n))
    for y in edges:
        if y != x:
            l = [l[y[0]-1] if l[i] == l[y[1]-1] else l[i] for i in range(n)]
    if len(set(l)) != 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def dfs(n,m,ls):
    stack = deque([1])
    visited = [0 for _ in range(n+1)]
    visited[0] = 1
    while stack:
        now = stack.pop()
        for i in range(1,n+1):
            if ls[now][i]==1 and visited[i]==0:
                stack.append(i)
        visited[now]=1
    if all(i==1 for i in visited):
        return True
    else:
        return False

if __name__ =="__main__":
    # n: 頂点, m: 辺
    n,m = map(int,input().split())
    ls = [[0 for _ in range(n+1)] for _ in range(n+1)]
    ls_inputs = [[int(x) for x in input().split()] for _ in range(m)]
    ans = 0
    for j in range(m):
        ls = [[0 for _ in range(n+1)] for _ in range(n+1)]
        for k,path in enumerate(ls_inputs):
            if j == k:
                pass
            else:
                ls[path[0]][path[1]]=1
                ls[path[1]][path[0]]=1
        if dfs(n,m,ls):
            pass
        else:
            ans +=1
    print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
N,M = map(int,input().split())
edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0]*(N+1) for _ in range(N+1)]
for a,b in edge:
  graph[a][b] = 1

answer = 0
INF = 10 ** 9
for a,b in edge:
  graph[a][b] = INF
  dist = dijkstra(graph, indices = a, directed = False)
  if dist[b] >= INF:
    answer += 1
  graph[a][b] = 1

print(answer)

Submission status: Accepted

Solution code:
ans = 0

N, M = map(int, input().split())
graph = [[0 for i in range(N)] for j in range(N)]
route = []

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

    route.append((a, b))

for a, b in route:
    graph[a-1][b-1] = 0
    graph[b-1][a-1] = 0

    visited = [False] * N
    visited[0] = True
    q = [i for i in range(N) if graph[0][i]]

    while q:
        r = q.pop(0)
        visited[r] = True
        for i in range(N):
            if graph[r][i] and not visited[i]:
                q.append(i)

    if False in visited:
        ans += 1
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
D = []
ans = 0
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  D.append((a,b))
for i in range(M):
  visited = [0]*N
  x,y = D.pop(i)
  C = [[] for i in range(N)]
  for j in range(M-1):
    a,b = D[j]
    C[a].append(b)
    C[b].append(a)
  H = deque()
  H.append(0)
  while H:
    e = H.popleft()
    if visited[e] == 0:
      visited[e] = 1
      for k in range(len(C[e])):
        H.append(C[e][k])
  D.insert(i,(x,y))
  if all(visited):
    continue
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]
        self.n = num

    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]

    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        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[y] += 1


def main():
    N, M = map(int, input().split())
    L = [list(map(int,input().split())) for i in range(M)]
    for i in range(M) :
        L[i][0] -= 1
        L[i][1] -= 1
    
    ans = 0
    
    for i in range(M) :
        UF = UnionFind(N)
        for j in range(M) :
            if j == i :
                continue
            UF.union(L[j][0], L[j][1])
        
        ans += (UF.same_root(L[i][0], L[i][1]) == False)
    
    print(ans)

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    main()

Submission status: Accepted

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

G = [[] for _ in range(N)]
for a, b in zip(A, B):
    G[a].append(b)
    G[b].append(a)

def dfs(F):
    E = []
    while F:
        v = F.pop()
        if v not in E:
            E.append(v)
        if len(E) == N:
            return True
        for e in G[v]:
            if e in E:
                continue
            F.append(e)

    return False

ans = 0
for a, b in zip(A, B):
    G[a].remove(b)
    G[b].remove(a)
    if not dfs([0]):
        ans += 1
    G[a].append(b)
    G[b].append(a)

print(ans)

Submission status: Accepted

Solution code:
# 2019/07/16

from heapq import heappop,heappush

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

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


def find(s,de):
    visited=[False]*n
    visited[s]=True
    que=[]
    for e in edge[s]:
        if s in de and e in de:continue
        heappush(que,e)
    while que: 
        v=heappop(que)
        if visited[v]:continue
        visited[v]=True
        for vtx in edge[v]:
            if v in de and vtx in de:continue
            if visited[vtx]:continue
            hq=vtx
            heappush(que,hq)

    if False in visited:
        return 1
    else:return 0

for i in range(m):
    tmp=del_edge[i]
    cnt+=find(0,tmp)

print(cnt)

Submission status: Accepted

Solution code:
from subprocess import*
with open('Main.java','w')as f:f.write(r"""
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static class Edge {
		int e1, e2;
		public Edge (int e1, int e2) {
			this.e1 = e1;
			this.e2 = e2;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		Edge[] c = new Edge[m];
		int ans = 0;
		for (int i = 0; i < m; i++)
			c[i] = new Edge(Integer.parseInt(sc.next()), Integer.parseInt(sc.next()));
		for (int i = 0; i < m; i++) {
			Edge[] d = new Edge[m - 1];
			for (int j = 0; j < i; j++)
				d[j] = c[j];
			for (int j = i; j < m - 1; j++)
				d[j] = c[j + 1];
			ans += search(n, d);
		}
		System.out.println(ans);
	}

	public static int search(int n, Edge[] d) {
		int[] already = new int[n + 1];
		Deque<Integer> p = new ArrayDeque<Integer>();
		already[d[0].e1] = 1;
		p.push(d[0].e1);
		int count = 1;
		while(!p.isEmpty()) {
			int here = p.pop();
			for (int i = 0; i < d.length; i++) {
				if (d[i].e1 == here && already[d[i].e2] != 1) {
					already[d[i].e2] = 1;
					p.push(d[i].e2);
					count++;
				}
				else if (d[i].e2 == here && already[d[i].e1] != 1) {
					already[d[i].e1] = 1;
					p.push(d[i].e1);
					count++;
				}
			}
		}
		if (count == n)
			return 0;
		else
			return 1;
	}
}
""")
call(('javac','Main.java'))
call(('java','Main'))

Submission status: Accepted

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

g=[[] for i in range(1+n)]
v=[0]*(1+n)
e=[]
for i in range(m):
    a,b=map(int,input().split())
    e.append((a,b))
    g[a].append(b)
    g[b].append(a)

def dfs(st,ed):
    q=[]
    q.append(st)

    while q:
        cur=q.pop()
        v[cur]=1
        if cur==ed:
            return True

        for nb in g[cur]:
            if v[nb]!=1 and (cur,nb)!=(st,ed):
                q.append(nb)
    return False

ans=0
for a,b in e:
    v=[0]*(1+n)
    if not dfs(a,b):
        ans+=1
print(ans)

Submission status: Accepted

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

g=[[] for i in range(1+n)]
v=[0]*(1+n)
e=[]
for i in range(m):
    a,b=map(int,input().split())
    e.append((a,b))
    g[a].append(b)
    g[b].append(a)

def dfs(st,ed):
    q=[]
    q.append(st)

    while q:
        cur=q.pop()
        v[cur]=1
        if cur==ed:
            return True

        for nb in g[cur]:
            #if v[nb]!=1:
            if v[nb]!=1 and (cur,nb)!=(st,ed):
                q.append(nb)
    #print(st,ed,v)
    return False

ans=0
for a,b in e:
    v=[0]*(1+n)
    #v[b]=1
    if not dfs(a,b):
        ans+=1
#print(g)
print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, id):
        self.id = id
        self.link = []

def bfs(node, check, ban_a, ban_b):
    check[node.id] = True
    ret = 1
    ban = -1
    if node.id == ban_a:
        ban = ban_b
    elif node.id == ban_b:
        ban = ban_a
    for next in node.link:
        if not check[next.id] and next.id != ban:
            ret += bfs(next, check, ban_a, ban_b)
    return ret





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

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

for i in range(M):
    a, b = ab[i]
    a -= 1; b -= 1;
    nodes[a].link.append(nodes[b])
    nodes[b].link.append(nodes[a])

ans = 0
root = nodes[0]
for i in range(M):
    a, b = ab[i]
    a -= 1; b -= 1;
    check = [False] * N
    if N != bfs(root, check, a, b):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
q=[i for i,gg in enumerate(g) if len(gg)==1]
cnt=0
while(q):
    cnt+=len(q)
    for i in q:
        g[i]=set()
        for j in range(N):
            g[j]=g[j]-{i}
    q=[i for i,gg in enumerate(g) if len(gg)==1]
print(min(cnt,M))

Submission status: Accepted

Solution code:
#幅優先探索（BFS）を利用
# 頂点と辺の数を入力する
N, M = map(int, input().split())
# 隣接リストを作成する
list_adjlist = [[] for _ in range(N + 1)]
# 辺のリストを作成する
list_edge = []
# 辺を入力し、隣接リストおよび辺のリストに格納する
for _ in range(M):
    a, b = map(int, input().split())
    list_edge.append((a, b))
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)

def FIFO(list_FIFO, node):
    if node != None:
        list_FIFO.append(node)
        return None
    return list_FIFO.pop(0)

# 橋の総数（all_bridge）を初期化する
all_bridge = 0

# uv間の辺がなくても、uからvへたどり着けるか探索
for u, v in list_edge:
    # uv間の辺が橋かどうか（uv_bridge）を初期化する（初期状態：1＝橋である）
    uv_bridge = 1
    # FIFOキューを初期化する
    list_FIFO = []
    # FIFOキューに入れたことのある点かどうかをチェックするリスト（list_check）を初期化する
    list_check = [False] * (N + 1)
    # FIFOキューにuを追加する
    FIFO(list_FIFO, u)
    # uをFIFOキューに入れた点としてチェックする
    list_check[u] = True
    # FIFOキューが空でない、かつvにたどり着いていない限り、幅優先探索
    while list_FIFO != [] and list_FIFO[-1] != v:
        # FIFOキューから点（node）を取り出す
        node = FIFO(list_FIFO, None)
        # nodeの隣接点（adjnode）について繰り返す
        for adjnode in list_adjlist[node]:
            # adjnodeがFIFOキューに入れたことのある点だった場合
            if list_check[adjnode]:
                # 以降の処理は行わずに次の隣接点に移る
                continue
            # adjnodeがvだった場合
            if adjnode == v:
                # nodeがuでない場合
                if node != u:  
                    # uv_bridgeを更新する（0＝橋でない）
                    uv_bridge = 0
                    # FIFOキューにadjnodeを追加する
                    FIFO(list_FIFO, adjnode)
                    # 繰り返しを終了する
                    break
            # adjnodeがv出ない場合
            else:
                # FIFOキューにadjnodeを追加する
                FIFO(list_FIFO, adjnode)
                # adjnodeをFIFOキューに入れた点としてチェックする
                list_check[adjnode] = True
    # all_bridgeにuv_bridgeを加える
    all_bridge += uv_bridge
                
# all_bridgeを出力する
print(all_bridge)

Submission status: Accepted

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

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

graph = [[] for _ in range(n)]
edge = []
for i in range(m):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    edge.append([a,b])
def dfs(g,s):
    c[s] = True
    for i in g[s]:
        if not c[i]:
            c[i] = True
            dfs(g,i)

check = [False]*n
ans = 0
for a,b in edge:
    c = check.copy()
    g = copy.deepcopy(graph)
    g[a-1].remove(b-1)
    g[b-1].remove(a-1)
    dfs(g,0)
    if False in c:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# 頂点と辺の数を入力する
N, M = map(int, input().split())
# 隣接リストを作成する
list_adjlist = [[] for _ in range(N + 1)]
# 辺のリストを作成する
list_edge = []
# 辺を入力し、隣接リストおよび辺のリストに格納する
for _ in range(M):
    a, b = map(int, input().split())
    list_edge.append((a, b))
    list_adjlist[a].append(b)
    list_adjlist[b].append(a)
    
# 橋の数bridgeを設定する
bridge = 0

# aとbを結ぶ辺について、その辺を通らずにaからbにたどり着けるかを調べる
for a, b in list_edge:
    # これから訪問する頂点のリストlist_nodeを初期化する
    list_node = list_adjlist[a].copy()
    list_node.remove(b)
    # これまでに訪問した頂点の集合set_visit_nodeを初期化する
    set_visit_node = {a}
    # 繰り返し
    while True:
        # 次に訪問可能な頂点の集合set_next_nodeを設定する
        set_next_node = set()
        # list_node内の頂点vに訪問する
        for v in list(list_node):
            # vと隣接している頂点をset_next_nodeに格納する
            set_next_node |= set(list_adjlist[v])
        # set_visit_nodeを更新する
        set_visit_node |= set(list_node)
        # set_next_nodeの全要素がset_visit_nodeに含まれる場合、、
        if set_next_node.issubset(set_visit_node):
            break
        # set_next_nodeの要素にset_visit_nodeに含まれない要素が存在する場合、、
        else:
            # list_nodeを更新する
            list_node = list(set_next_node - set_visit_node)
    # set_visit_nodeにbが含まれない場合（＝aからbにたどり着けない場合）
    if b not in set_visit_node:
        bridge += 1

# 結果を出力する
print(bridge)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    c[a].append(b)
    c[b].append(a)
def des(c,res):
    for i in range(1,n+1):
        if len(c[i])==1:
            c[c[i][0]].remove(i)
            c[i]=[]
            res=des(c,res+1)
    return res
print(des(c,0))

Submission status: Accepted

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]

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


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

    def merge(self, x, y):
        x, y = self.find_root(x), self.find_root(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    def issame(self, x, y):
        return self.find_root(x) == self.find_root(y)


    def get_size(self, x):
        x = self.find_root(x)
        return self.size[x]

ans = 0
data = []
for i in range(M):
    a, b = [int(_) for _ in stdin.readline().rstrip().split()]
    a, b = a-1, b-1
    data.append((a, b))

for i in range(M):
    uf = UnionFind(N)
    for j in range(M):
        if i == j:
            continue
        uf.merge(data[j][0], data[j][1])
    flag = False
    for j in range(N):
        if not uf.issame(0, j):
            flag = True
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
node=[None for i in range(m)]#辺のデータをリストとして保管
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(m):
    a,b=map(int,input().split())
    graph[a-1][b-1],graph[b-1][a-1]=True,True
    node[i]=[a-1,b-1]
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
ans=0
for i in range(m):
    graph[node[i][0]][node[i][1]],graph[node[i][1]][node[i][0]]=False,False #m本の辺について、一本ずつ辺を無視していく。その際にグラフが非連結となったらその辺は橋となる（橋の定義通り調べていく）
    for j in range(n):visited[j]=False#初期化
    dfs(0)
    for h in range(n):
        if visited[h]==False:
            ans+=1
            break
    graph[node[i][0]][node[i][1]],graph[node[i][1]][node[i][0]]=True,True#調査が終わったら戻しておく
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
v=[]
for i in range(m):
    a,b=map(int,input().split())
    v.append((a-1,b-1))
def dfs(x):
    check[x]=True
    for i in graph[x]:
        if not check[i]:
            dfs(i)
ans=0
for i in range(m):
    graph=[[] for i in range(n)]
    for j in range(m):
        if j!=i:
            graph[v[j][0]].append(v[j][1])
            graph[v[j][1]].append(v[j][0])
    check=[False]*n
    dfs(0)
    for j in check:
        if not j:
            ans+=1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
    
    def root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
 
        return self.par[x]
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
 
ans = 0
for i in range(M):
    Path = AB[:i] + AB[i+1:]
    uf = UnionFind(N)
    for x, y in Path:
        uf.union(x, y)

    count = 0
    for j in range(1, N+1):
        if uf.par[j] == j:
            count += 1
            if count >= 2:
                ans += 1
                break
    
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[-1 for i in range(n)]    #par<0なら自身が親で要素の個数、>0なら子で親の位置示す

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

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

def connect(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

a=[]
for i in range(m):
    a.append([int(j)-1 for j in input().split()])

ans=0
for i in range(m):
    par=[-1 for i in range(n)] 
    for j in range(m):
        if j==i:
            continue
        if root(a[j][0])!=root(a[j][1]):
            connect(a[j][0],a[j][1])
    if -1*min(par)!=n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

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

ab = []
ans = 0

for i in range(M):

    a,b = map(int,input().split())
    ab.append([a,b])

for i in range(M):

    abc = ab.copy()
    del abc[i]

    lis = [1] + [0] * (N-1)

    flag = True

    while flag:

        flag = False

        for j in abc:

            if lis[ j[0]-1 ] == 1:
                lis[ j[1]-1 ] = 1
                abc.remove(j)
                flag = True
                break

            elif lis[ j[1]-1 ] == 1:
                lis[ j[0]-1 ] = 1
                abc.remove(j)
                flag = True
                break

    #print (lis)
    if 0 in lis:
        ans += 1

print (ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
side = [list(map(int, input().split())) for i in range(M)]
maze = [[0] * N for i in range(N)]


for i, j in side:
    maze[i-1][j-1] = 1
    maze[j-1][i-1] = 1


visited = [0] * N

def search_side(maze, v):
    ans = []
    for i in range(len(maze[v])):
        if maze[v][i] == 1:
            ans.append(i)
    return ans

def dfs(v, visited, maze):
    visited[v] = 1
    for i in search_side(maze, v):
        if visited[i] == 1:
            continue
        else:
            visited = dfs(i, visited, maze)
    return visited

ans = 0
for i, j in side:
    maze[i-1][j-1] = 0
    maze[j-1][i-1] = 0
    if sum(dfs(0, visited, maze)) != N:
        ans += 1
    maze[i-1][j-1] = 1
    maze[j-1][i-1] = 1
    visited = [0] * N
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[]
for i in range(m):
    p.append(list(map(int,input().split())))
g=[[] for i in range(n+1)]
for pi in p:
    g[pi[0]].append(pi[1])
    g[pi[1]].append(pi[0])
def dfs(v,visited,g):
     for v2 in g[v]:
         if visited[v2]==0:
             visited[v2]=1
             dfs(v2,visited,g)

c=0
for pi in p:
    g[pi[0]].remove(pi[1])
    g[pi[1]].remove(pi[0])
    visited=[0]*(n+1)
    visited[0]=1
    visited[1]=1
    dfs(1,visited,g)
    if 0 in visited:
        c+=1
    g[pi[0]].append(pi[1])
    g[pi[1]].append(pi[0])
print(c)

Submission status: Accepted

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

def test(k):
    d = {i + 1 : [] for i in range(n)}
    for i, (a, b) in enumerate(es):
        if i == k:
            continue
        d[a].append(b)
        d[b].append(a)
    q = [1]
    visited = set([])
    while True:
        if len(q) == 0:
            if len(visited) == n:
                return 0
            else:
                return 1
        q2 = q[:]
        q = []
        for v in q2:
            if v not in visited:
                visited.add(v)
                q.extend(d[v])
ans = 0
for k in range(m):
    ans += test(k)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
T = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a][b] = 1
    T[b][a] = 1
ans = 0
def f(v,x,y):
    global N,M,T,a
    a[v] = 1
    for i in range(N+1):
        if (v==x and i==y) or (v==y and i==x):
            continue
        elif T[v][i]==0 or a[i]==1:
            continue
        f(i,x,y)
for i in range(1,N+1):
    for j in range(i,N+1):
        a = [0 for _ in range(N+1)]
        f(1,i,j)
        if sum(a)!=N:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
#グラフが連結かどうかをDFSで判定する
def dfs(g, v):
    visited[v] = True
    for v2 in range(N):
        if visited[v2] == False and g[v][v2] == 1:
            dfs(g,v2)

##入力
N, M = map(int,input().split())
#隣接行列を作る
graph = [[0 for i in range(N)] for j in range(N)]
edgelist = [] #辺のリスト
for e in range(M):
    ai, bi = map(int,input().split())
    graph[ai-1][bi-1] = 1
    graph[bi-1][ai-1] = 1
    edgelist.append([ai-1,bi-1])

bridges = 0 #橋の数
#辺を一本ずつ外して連結かどうか判定
for edge in edgelist:
    #辺を削除
    graph[edge[0]][edge[1]] = 0
    graph[edge[1]][edge[0]] = 0
    
    isbridge = False
    visited = [False for i in range(N)]
    dfs(graph, 0)
    
    for i in range(N):
        if visited[i] == False:
            isbridge = True
            break
    if isbridge == True:
        bridges += 1
    
    #削除した辺を戻す
    graph[edge[0]][edge[1]] = 1
    graph[edge[1]][edge[0]] = 1

print(bridges)

Submission status: Accepted

Solution code:
class UnionFind() :
	
	def __init__(self,n) :  #n要素で初期化
		#親要素のノード番号を格納。par[x]==xの時そのノードは根
		self.par = [i for i in range(n+1)];
		self.rank = [0]*(n+1);
	
	def root(self,x) :  #木の根を求める
		if self.par[x] == x :  #根
			return x;
		else :
			self.par[x] = self.root(self.par[x]);  #経路圧縮
			return self.par[x];
	
	def unite(self,x,y) :  #xとyの属する集合を併合
		x = self.root(x);
		y = self.root(y);
		if x == y :
			return;
		
		if self.rank[x] < self.rank[y] :  #ランクに関する処理
			self.par[x] = y;
		else :
			self.par[y] = x;
			if self.rank[x] == self.rank[y] :
				self.rank[x] += 1;
	
	def same_check(self,x,y) :  #xとyが同じ集合に属するか否か
		return self.root(x) == self.root(y);

nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
ab = [[0]*2 for i in range(m)];
for i in range(m) :
	s = input().split(" ");
	ab[i][0] = int(s[0]);
	ab[i][1] = int(s[1]);

basefin = UnionFind(n);
check_base = [0]*(n+1);
for i in range(m) :
	basefin.unite(ab[i][0],ab[i][1]);
for i in range(1,n+1) :
	check_base[basefin.root(i)] = 1;
base = sum(check_base);

ans = 0;
for i in range(m) :
	unifin = UnionFind(n);
	check = [0]*(n+1);
	for j in range(m) :
		if j != i :
			unifin.unite(ab[j][0],ab[j][1]);
	for k in range(1,n+1) :
		check[unifin.root(k)] = 1;
	if sum(check) - base == 1 :
		ans += 1;
	
print(ans);

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
g = [[] for i in range(n)]
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

u = 0
s = []
non_bridge = []
while True:
    if u in s:
        tmp = s[s.index(u):]
        tmp.append(u)

        if len(tmp)>=4:
            for i in range(len(tmp)-1):
                if sorted(tmp[i:i+2]) not in non_bridge:
                    non_bridge.append(sorted(tmp[i:i+2]))
        u = s.pop()
    elif len(g[u]) > 0:
        s.append(u)
        j = -1
        for i in range(len(g[u])):
            if g[u][i] not in s:
                j = i
        u = g[u].pop(j)
    else:
        if len(s) == 0:
            break
        u = s.pop()

print(m-len(non_bridge))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.rank = [0 for _ in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            elif self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    temp = ab[:i] + ab[i+1:]
    for a, b in temp:
        uf.union(a-1, b-1)
    
    for i in range(N-1):
        if uf.is_same(i, i+1) == False:
            ans += 1
            break

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
   def __init__(self,n):
       self.parent = [-1 for i in range(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, y = self.find(x), self.find(y)
       if (x == y):
           pass
       else:
           self.parent[x] = self.parent[y]
           self.parent[y] = x

   def isgroup(self, x, y):
       return True if self.find(x) == self.find(y) else False

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

ans = 0
for i in range(M):
    uf = UnionFind(N)
    temp = ab[:i] + ab[i+1:]
    for a, b in temp:
        uf.union(a-1, b-1)

    for i in range(1, N):
        if uf.isgroup(i, i-1) == False:
            ans += 1
            break

print(ans)