Hackerrank GraphTheory Roads and

The Ruler of HackerLand believes that every citizen of the country should have access to a library. Unfortunately, HackerLand was hit by a tornado that destroyed all of its libraries and obstructed its roads! As you are the greatest programmer of HackerLand, the ruler wants your help to repair the roads and build some new libraries efficiently.

HackerLand has n cities numbered from 1 to n . The cities are connected by m bidirectional roads. A citizen has access to a library if:

1.Their city contains a library.
2.They can travel by road from their city to a city containing a library.

input format：
第一行是q表示q个query，请求。
然后每个请求第一行有四个数字 分别是 n, m ,c_lib, c_road
n是城市数量，m是道路数量，c_lib,c_road分别是维修图书馆和维修道路的费用。

一开始这题确实看起来很复杂的，感觉不知道该往哪里放图书馆或者放道路，但实际上这题并不需要考虑那么多，只需要考虑两种情况：

第一个是如果维修道路的费用要高于维修图书馆的费用，那么你根本不要维修道路，直接每个城市都维修图书馆。显然这是费用最少的方法。

第二个是图书馆的费用比道路的费用高，那么这个时候，你可以把任何可以维修道路的城市都看作一个连通子图，我们在这个连通子图里求一个最小生成树，维修最小生成树的道路的费用再加上一个图书馆的费用，就是这个情况下最小的方案。

为什么？一个有n个节点的子图，最小生成树必然是n-1条。如果我们接着把这个连通子图拆成两个更小的连通子图的话，比如我们去掉其中一条路，那么我们就要多修一个c_lib，显然c_lib > c_road，所以我们要花费更多的费用。

在第二种情况下 最低费用为 sigma [ (连通子图的数量-1) * c_road + c_lib]

那么怎么数每个连通子图的结点数量？简单地用bfs数就行

代码如下:

def bfs(city,visited,adjlist):
    que = []
    cnt = 0
    if visited[city-1]==0:
        que.append(city)
        visited[city-1]=1
        cnt+=1
        while len(que)!=0:
            node = que[0]
            #print(node)
            for i in adjlist[node-1]:
                if visited[i-1]==0:
                    que.append(i)
                    visited[i-1]=1
                    cnt+=1
            del que[0]
    #print(visited) 
    return cnt
    

# Complete the roadsAndLibraries function below.
def roadsAndLibraries(n, c_lib, c_road, cities):
    if c_lib<c_road:
        return n*c_lib
    else:
        visited = [0]*n
        adjlist = [[] for i in range(n)]
        for x,y in cities:
            adjlist[x-1].append(y)
            adjlist[y-1].append(x)

        ans = 0
        for city in range(1,n+1):
            #print(city)
            if not visited[city-1]:
                tmp=bfs(city,visited,adjlist)
                if tmp==1:
                    ans+=c_lib
                elif tmp>1:
                    ans+=(tmp-1)*c_road+c_lib   
        return ans