city-and-fireman-vincent

Fatland is a town with N cities numbered 1, 2, ..., N, connected with 2-way roads. Vincent is a villian who wants to set the entire town ablaze. For each city, there is a certain risk factor E[i] for setting that city ablaze. But once a city c is set ablaze, all cities that can be reached from c will be set ablaze immediately.

The overall risk factor of setting some number of cities ablaze is the sum of the risk factors of setting each of the cities ablaze. Vincent's goal is to set the whole town ablaze with minimal risk by picking some set of cities to set ablaze. Let M be the minimum risk he takes when setting the entire city ablaze. Calculate the number of ways to pick a set of cities to obtain a risk of M. 

Input:

The first line contains an integer N, the number of cities in Fatland.

The second line contains N space-separated integers, the i-th integer representing E[i]. (1-based index)

The third line contains an integer K, denoting the number 2-way roads.

Each of the next K lines contains 2 space-separated integers i, j, a road between cities i and j.

Output: Output one integer, W. The number of ways to pick a set of cities to obtain a risk of M, so that the entire town is set ablaze is U. W is the remainder when U is divided by 10^9+7=1000000007.

Constraints:

1 ≤ N ≤ 10^3

1 ≤ K ≤ 10^3

1 ≤ E[i] ≤ 10^3

SAMPLE INPUT
4
3 3 3 3
2
1 2
4 1

SAMPLE OUTPUT
3

Explanation

Vincent can set cities 1 and 3 ablaze, 2 and 3 ablaze, or 4 and 3 ablaze for a risk of 6. Note that setting either 1, 2, 4 ablaze will set 1, 2, and 4 ablaze.

Source: hackerearth | Difficulty: EASY
Tags: Spanning trees


Solutions:
import sys

def MakeSet(x):
	x.parent = x
	x.rank   = 0

def Union(x, y):
	xRoot = Find(x)
	yRoot = Find(y)
	if xRoot.rank > yRoot.rank:
	    yRoot.parent = xRoot
	elif xRoot.rank < yRoot.rank:
	    xRoot.parent = yRoot
	elif xRoot != yRoot: # Unless x and y are already in same set, merge them
	    yRoot.parent = xRoot
	    xRoot.rank = xRoot.rank + 1

def Find(x):
	if x.parent == x:
	   return x
	else:
	   x.parent = Find(x.parent)
	   return x.parent

class Node:
    def __init__ (self, label, risk):
	   self.label = label
	   self.risk = risk

    def __str__(self):
	   return str(self.label)

ff = sys.stdin

N = int(ff.readline())

M = pow(10, 9) + 7

E = [int(x) for x in ff.readline().split()]

K = int(ff.readline())

node_list = [Node(x, E[x-1]) for x in range(1,N+1)]

for node in node_list :
    MakeSet(node)

for k in range(K):
    i,j = [int(x) for x in ff.readline().split()]
    Union(node_list[i-1], node_list[j-1])


d = dict()

for x in node_list :
    r = Find(x)
    # print("r: %s"%(r,))
    yy = d.get(r , [1001,0])
    
    # print("yy: %s, x.risk : %d"%(yy,x.risk))
    if x.risk <= yy[0]:
	   # print("yes")
	   if yy[0] == x.risk :
		  yy[1] += 1
	   else :
		  yy[1] = 1
		  yy[0] = x.risk

    d[r] = yy

total = 1
# for x in node_list:
#     print(str(x))

# for key in d :
#     print(str(key) + ":" + str(d[key]))

for key in d:
    total = (total * d[key][1]) %  M

print(total)











import collections

MOD = 1000000007

def union(parents, depths, i, j):
	''' Union with under the deepest root '''
	if depths[i] > depths[j]:
		parents[j] = i
	else:
		parents[i] = j
		depths[i] = max(depths[i], depths[j] + 1)

def find(parents, el):
	''' Find an element and compress the sets '''
	if parents[el] == el: return el
	leader = find(parents, parents[el])
	parents[el] = leader
	return leader

def solve(risks, roads):
	depths = [1] * len(risks)
	parents = list(range(0, len(risks)))
	for a, b in roads:
		union(parents, depths, find(parents, a - 1), find(parents, b - 1))

	clusters_min_count = collections.defaultdict(lambda: [float('inf'), 0])
	for city in range(0, len(risks)):
		root = find(parents, city)
		if risks[city] < clusters_min_count[root][0]:
			clusters_min_count[root] = [risks[city], 1]
		elif risks[city] == clusters_min_count[root][0]:
			clusters_min_count[root][1] += 1
	count = 1
	for _, nb in list(clusters_min_count.values()):
		count = (count * nb) % MOD
	return count

if __name__ == '__main__':
	input()
	xs = list(map(int, input().split()))
	xss = [list(map(int, input().split())) for _ in range(int(input()))]
	print(solve(xs, xss))


def dfs(adj,visited,s,e):
	stack=[]
	stack.append(s)
	visited[s]=True
	minrisk = e[s]
	count=1
	while len(stack)!=0:
		v = stack.pop()
		for i in range(len(adj[v])):
			if not visited[adj[v][i]]:
				stack.append(adj[v][i])
				visited[adj[v][i]]=True
				if e[adj[v][i]]<minrisk:
					minrisk=e[adj[v][i]]
					count=1
				elif e[adj[v][i]]==minrisk:
					count+=1	
	return count


n = int(input())
e = list(map(int,input().split()))
adj = [[] for i in range(n)]
visited=[False for i in range(n)]
k = int(input())
count=0
ans=1
countarr=[]
for i in range(k):
	x,y = list(map(int,input().split()))
	x=x-1
	y=y-1
	if y not in adj[x]:
		adj[x].append(y)
		adj[y].append(x)
for i in range(n):
	if not visited[i]:
		count=dfs(adj,visited,i,e)
		ans*=count
print(ans%1000000007)			


from functools import reduce
def root(dsj_set, n):
	k = n
	while n != dsj_set[n]:
		n = dsj_set[n]
	while k != n:
		x = dsj_set[k]
		k = dsj_set[x]
		dsj_set[x] = n
	return n

def root2(dsj_set, n):
	while n != dsj_set[n]:
		n = dsj_set[n]
	return n

def union(dsj_set, size, aroot, broot):
	if size[aroot] < size[broot]:
		dsj_set[aroot] = broot;
		size[broot] += size[aroot]
	else:
		dsj_set[broot] = aroot
		size[aroot] += size[broot]

n = eval(input())
ary = [int(i) for i in input().strip().split()]
dsj_set = list(range(n+1))
size = [1]*(n+1)
q = eval(input())
for i in range(q):
	a,b = list(map(int, input().strip().split()))
	aroot = root(dsj_set, a)
	broot = root(dsj_set, b)
	union(dsj_set, size, aroot, broot)

for z in range(len(dsj_set)):
	rt = root2(dsj_set, dsj_set[z])
	if rt != dsj_set[z]:
		dsj_set[z] = rt

x = set(dsj_set)
x.discard(0)
x = list(x)
counter = []
#print x
#print dsj_set
#print "i am here."

for c in x:
	mn = 10000
	count = 0
	for j in range(1,len(dsj_set)):
		if dsj_set[j] == c and ary[j-1] < mn:
			mn = ary[j-1]
	for l in range(1,len(dsj_set)):
		if dsj_set[l] == c and ary[l-1] == mn:
			count += 1
	counter.append(count)
#print counter
print(reduce(lambda x,y:x*y, counter)%(10**9+7))
#print "done"


N = int(input())

arr = []
size = []


def initialize(arr, n):
	for i in range(n):
		arr.append(i)
		size.append(1)
		



initialize(arr, N)

e = list(map(int, input().strip().split(" ")))


def root(arr, i):
	while arr[i] != i:
		arr[i] = arr[arr[i]]
		i = arr[i]
	return i


def union(arr, size, a, b):
	root_a = root(arr, a)
	root_b = root(arr, b)
	if size[root_a] < size[root_b]:
		arr[root_a] = arr[root_b]
		size[root_b] += size[root_a]
	else:
		arr[root_b] = arr[root_a]
		size[root_a] += size[root_b]
		
def root(arr, i):
	while arr[i] != i:
		arr[i] = arr[arr[i]]
		i = arr[i]
	return i


K = int(input())

for i in range(K):
	a, b = list(map(int, input().strip().split(" ")))
	union(arr, size, a-1, b-1)
	
mp = {}
for i in range(N):
	mp[root(arr, i)] = mp.get(root(arr, i), []) + [e[i]]
	
ans = 1
for v in list(mp.values()):
	m = min(v)
	cnt=0
	for i in v:
		if i == m:
			cnt+=1
	ans = ans * cnt
	
print(ans % 1000000007)



from collections import defaultdict
N = int(input())
risk = list(map(int, input().split(" ")))
risk.insert(0, 0)
K = int(input())
adj = defaultdict(list)
visited = [False]*(N+1)
def bfs(i):
	visited[i] = True
	q = [i]
	min_risk = risk[i]
	city_count = 0
	while q:
		node = q[0]
		q = q[1:]
		if risk[node] < min_risk:
			min_risk = risk[node]
			city_count = 1
		elif risk[node] == min_risk:
			city_count += 1
		for neighbour in adj[node]:
			if not visited[neighbour]:
				q.append(neighbour)
				visited[neighbour] = True
	return city_count
min_risk = 1000000000000000000
city_count = 0
def dfs(node):
	global min_risk
	global city_count
	visited[node] = True
	if risk[node] < min_risk:
		min_risk = risk[node]
		city_count = 1
	elif risk[node] == min_risk:
		city_count += 1
	for neighbour in adj[node]:
		if not visited[neighbour]:
			dfs(neighbour)

for i in range(K):
	i, j = list(map(int, input().split(" ")))
	adj[i].append(j)
	adj[j].append(i)
count = 1
for i in range(1, N+1):
	min_risk = 1000000000000000000
	city_count = 0
	if not visited[i]:
		ans = bfs(i)
		#print "Ans ", city_count
		count *= ans
print(count%1000000007)


from functools import reduce
#!/usr/bin/env python
# encoding: utf-8

MOD = int(1e9 + 7)
fa, Min, cnt = [], [], []

def findfa(x):
	if x == fa[x]:
		return x
	else:
		fa[x] = findfa(fa[x])
		return fa[x]

if __name__ == '__main__':
	N = int(input())
	E = list(map(int, input().split()))
	K = int(input())
	fa = [i for i in range(N)]
	Min = [E[i] for i in range(N)]
	cnt = [1 for i in range(N)]
	for _ in range(K):
		i, j = list(map(int, input().split()))
		i -= 1
		j -= 1
		x, y = findfa(i), findfa(j)
		if x != y:
			fa[x] = y
			if Min[x] == Min[y]:
				cnt[y] += cnt[x]
			elif Min[x] < Min[y]:
				Min[y] = Min[x]
				cnt[y] = cnt[x]
	print(reduce(lambda a, b: a * b % MOD, [cnt[i] for i in range(N) if findfa(i) == i], 1))


from collections import defaultdict

class Graph():

	def __init__(self, connections=[], directed=False):
		self.status_dict      = defaultdict(lambda : 1)
		self.graph_dict       = defaultdict(list)
		self.is_directed      = directed
		

	def add_edge(self,node1, node2):
	   
		self.graph_dict[node1].append(node2)
			
		if not self.is_directed:
			self.graph_dict[node2].append(node1)
				
	   
	def add_vertex(self,node):
		self.graph_dict[node]
		self.status_dict[node]



def dfs(g,src_node):
	global E
	risk_dict               = defaultdict(list)
	stack                   = []
	stack.append(src_node)
	g.status_dict[src_node] = 2 
	
	while len(stack) != 0:
		node = stack.pop()
		risk = E[node-1]
		risk_dict[risk].append(node)
		g.status_dict[node] = 3;
		#print node,
	
		for nbs in g.graph_dict[node]:
			if g.status_dict[nbs]  == 1:
				stack.append(nbs)
				g.status_dict[nbs] = 2
				
	return len(list(risk_dict.values())[0])
	
	
def connected_components(g):
	connected_components = 0
	ans=1
	for node in list(g.graph_dict.keys()):
		if g.status_dict[node]   == 1:
			ans*=dfs(g,node)
			connected_components +=1    
	return ans

N = int (input())
g = Graph()

for i in range(N):
	g.add_vertex(i)

E = [int(x) for x in input().split()]

K = int (input())

for i in range(K):
   node1,node2 = [int(x) for x in input().split()]
   g.add_edge(node1,node2)

print(int(connected_components(g)%(1000000007)))