Treasure 1 - MarisaOJ: Marisa Online Judge

Marisa has recently found a treasure map that leads her to an underground cave system consisting of

n

$n$ rooms and

m

$m$ one-way tunnels. The cave is so dark that Marisa needs to use her power to light it up. If she lights up a room

i

$i$ , room

j

$j$ can receive the light if

j

$j$ can be reached from

i

$i$ and

i

$i$ can also be reached in

j

$j$ . The cost of lighting up room

i

$i$ is

A_{i}

$A_i$ power. What is the minimum amount of power needed to completely eliminate the darkness in the cave? ### Input - The first line contains 2 integers

n, m

$n,m$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

m

$m$ lines, each line contains two integers

u, v

$u, v$ , there is a tunnel between

u

$u$ and

v

$v$ . ### Output - Print the minimum amount of power. ### Constraints -

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

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

1 \leq A_{i} \leq 10^{9}

$1 \le A_i \le 10^9$ . -

1 \leq u, v \leq n

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

33123122331

$3 3 1 2 3 1 2 2 3 3 1$

Output:

1

$1$

Strongly connect component
	Reachability
	Treasure 1
	Treasure 2

Topic

Graph

Rating

1400

Solution (0)

Solution