畅通工程

[编程题]畅通工程

热度指数：12731 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入描述:

    测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
    注意:两个城市之间可以有多条道路相通,也就是说
    3 3
    1 2
    1 2
    2 1
    这种输入也是合法的
    当N为0时，输入结束，该用例不被处理。

输出描述:

    对每个测试用例，在1行里输出最少还需要建设的道路数目。

示例1

输入

输出

算法知识视频讲解

Python

lx的流星

while True:
    try:
        n,m=map(int,input().strip().split(' '))
        if m==0:
            print(n-1)
        else:
            road=[]
            for i in range(m):
                road.append(list(map(int,input().strip().split(' '))))
            list1=[]
            list2=[]
            for i in range(m):
                new_road=road[0:i]+road[i+1:]
                for j in range(len(new_road)):
                    index=set(road[i]).intersection(set(new_road[j]))
                    if len(index)!=0:
                        #print(road[i])
                        #print(road[j])
                        if road[i] not in list2 and road[i][::-1] not in list2:
                            list2.append(road[i])
                            break
            for i in road:
                if i not in list2 and i[::-1] not in list2:
                    list1.append(i)
            if len(list2)!=0:
                num1=len(list1)+1
            else:
                num1=len(list1)
            #print(num)
            #print(list1)
            #print(list2)
            num2=0
            list1_1=[]
            list2_1=[]
            for i in list1:
                list1_1+=i
            for i in list2:
                list2_1+=i
            list3=list(set(list1_1))+list(set(list2_1))
            for i in range(1,n+1):
                if i not in list3:
                    num2+=1
            result=num1+num2-1
            print(result)
    except:
        break

发表于 2019-07-30 21:06:20 回复(0)

Python

TimeMac

和最小生成树思想差不多，找到这些城镇节点能构成多少颗树，就需要造树的数量-1条道路。

找出边的结点的根是否一样，不一样表示这两个数可以通过这条边联结为一颗树。

while True:
    try:
        def findRoot(b):    #找树根
            global roads
            if roads[b] == 0:                #树根为0表示自己为根
                return b
            else:
                temp = findRoot(roads[b])
                roads[b] = temp
                return temp
        town,roadNum = list(map(int,input().split()))
        roads = [0 for i in range(town+1)]   #一开始每个树根为0,0下标我没用
        for i in range(roadNum):
            tempInput = list(map(int, input().split()))
            a = findRoot(tempInput[0])       #找出两个新来边的结点的根是否相同
            b = findRoot(tempInput[1])
            if a != b:                       #如果根不一样，这条路把他们连接到一起，两棵树缩成一棵树
                roads[a] = b
        print(roads.count(0)-2)   #0的数量减去1（下标为0的值为0）得到树的棵数，再减一得到需要造的路
    except Exception:
        break

编辑于 2018-09-25 15:32:38 回复(0)