Bridge Minimization - ReimuOJ: Reimu Online Judge

HOME
PROBLEMSET
ROADMAP
COMPETITION
TOPIC
RANKING
GUIDE
MASHUP
ABOUT
CONTACT

Given a simple, undirected graph with

n

$n$ vertices and

m

$m$ edges, determine the maximum number of bridges that can be reduced after adding an edge to the graph. ### Input - The first line contains 2 integers

n, m

$n,m$ . - The next

m

$m$ lines, each line contains two integers

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . ### Output - Print the maximum number of bridges can be reduced. ### Constraints -

1 \leq n, m \leq 10^{5}

$1 \le n,m \le 10^5$ . -

1 \leq u, v \leq n

$1 \le u,v \le n$ . ### Example Input:

651323344546

$6 5 1 3 2 3 3 4 4 5 4 6$

Output:

3

$3$

Articulation point and bridge
	Articulation point
	Bridge
	Articulation point and bridge
	Bridge Minimization
	Unique path

Topic

Graph

Rating

1400

Solution (1)

Solution