2018 Google kickstart Problem A. Planet Distance

拼搏现实的明天。 2022-05-24 12:44 43阅读 0赞

# 题目描述 #

![题目描述][70]

Small dataset
    3 ≤ N ≤ 30.
    Large dataset
    3 ≤ N ≤ 1000.
    
    
    input
    2
    5
    1 2
    2 3
    3 4
    2 4
    5 3
    3
    1 2
    3 2
    1 3
    
    Output 
    Case #1: 1 0 0 0 1
    Case #2: 0 0 0
    
    In Sample Case #1, the cycle consists of planets 2, 3, and 4. Therefore, the distances for planets 2, 3, and 4 are 0. There is a vacuum tube between 1 and 2, and another vacuum tube between 3 and 5. Thus, planets 1 and 5 are at a distance 1 from the cycle.
    
    In Sample Case #2, all the planets are part of the cycle. Hence, their distances are 0.

题目大致意思是，有很多星球，在每个星期之间会有管道，当这些管道和星球形成环的时候，这些形成环的星球上会有一些礼物，这些形成环的星球离礼物的距离为0，其它星球离礼物的距离，是到形成环的所有星球中距离最短的那条，求所有星球到礼物的距离。

# 解题思路 #

这题主要是找到有环无向图上的所有节点距离环的最短距离, 可以先用DFS找到环上的点，然后去BFS去求每个节点到环上的距离。

# 代码： #

# -*- coding: utf-8 -*-
    
    # !/usr/bin/env python
    
    # Time: 2018/5/27 13:34
    
    # Author: sty
    
    # File: A Planet Distance.py
    
    
    from collections import defaultdict
    
    
    # This class represents a undirected graph using adjacency list representation
    class Graph:
    
        def __init__(self, vertices, dis, res):
            self.V = vertices  # No. of vertices
            self.distance = dis
            self.res = res
            self.graph = defaultdict(list)  # default dictionary to store graph
    
        # function to add an edge to graph
        def addEdge(self, v, w):
            self.graph[v].append(w)  # Add w to v_s list
            self.graph[w].append(v)  # Add v to w_s list
    
        # A recursive function that uses visited[] and parent to detect
        # cycle in subgraph reachable from vertex v.
        def isCyclicUtil(self, v, visited, parent):
    
            # Mark the current node as visited
            visited[v] = True
    
            # Recur for all the vertices adjacent to this vertex
            for i in self.graph[v]:
                # If the node is not visited then recurse on it
                if visited[i] == False:
                    if (self.isCyclicUtil(i, visited, v)):
                        return True
                # If an adjacent vertex is visited and not parent of current vertex,
                # then there is a cycle
                elif parent != i:
                    self.res.append(v)
                    return True
    
            return False
    
        # Returns true if the graph contains a cycle, else false.
        def isCyclic(self):
            # Mark all the vertices as not visited
            visited = [False] * (self.V + 1)
            # Call the recursive helper function to detect cycle in different
            # DFS trees
            for i in range(1, self.V + 1):
                if visited[i] == False:  # Don't recur for u if it is already visited
                    if (self.isCyclicUtil(i, visited, -1)) == True:
                        return True
            return False
    
    
    
        def judge(self, u, v):
            visited = [False] * (self.V + 1)
            distance = [0 for i in range(self.V + 1)]
            queue = []
            queue.append(u)
            visited[u] = True
            while queue:
                x = queue.pop(0)
                for i in self.graph[x]:
                    if visited[i] == False:
                        distance[i] = distance[x] + 1
                        queue.append(i)
                        visited[i] = True
            return distance[v]
    
    
        def count_dis(self):
            cycle_list = []
            for i in self.graph[self.res[0]]:
                cycle_list.append(i)
            cycle_list.append(self.res[0])
            visited = [False] * (self.V + 1)
            for i in range(1, self.V + 1):
                if i in cycle_list:
                    self.distance[i] = 0
                else:
                    len_min = self.V + 1
                    for j in cycle_list:
                        tem_min = self.judge(i, j)
                        if tem_min < len_min:
                            len_min = tem_min
                    self.distance[i] = len_min
    
    
    if __name__ == '__main__':
        # input() reads a string with a line of input, stripping the '\n' (newline) at the end.
        # This is all you need for most Kickstart problems.
        t = int(input())  # read a line with a single integer
        for ti in range(1, t + 1):
            n = int(input())
            dis = [0 for i in range(n + 1)]
            res = []
            g = Graph(n, dis, res)
            for i in range(n):
                n, m = [int(s) for s in input().split(" ")]
                g.addEdge(n, m)
            if g.isCyclic():
                g.count_dis()
                print("Case #{0}:".format(ti), end='')
                for x in dis[1:]:
                    print(' ',x, end='')
                print('\n', end='')
    
    
    
            # check out .format's specification for more formatting options

输入文件在[这里][Link 1]，大家感兴趣可以测试下

# 后记 #

这是Google 2018的kickstart在线测试题,如果不知道这个测试题的同学可以自行百度，这次总共三道题，很可惜，我只做了第一道题，而且最后测试，虽然我感觉没什么问题，但是提示我错误了。总体感觉Google的kickstart题目考察范围十分的有内涵，一道题里面可能有好几个知识点，但是也看见有大神不到半个小时就把三个题都做了的，总的来说还是自己太水。  
随便吐槽下kickstart的做题方式是要自己将输入测试集下载下来，然后提交输出结果集和程序上去，判断错误，感觉这样的过程很是麻烦。

[70]: /images/20220524/2a7a4a69650245f3809d5c1d1053a0dd.png
[Link 1]: https://download.csdn.net/download/sty945/10440836