上一个博客我们讲了原题是怎么做的，现在我想超级加倍一下，修改一下原题，改成总分100，然后数一下，一个环两分，这样题就变难了好多，但是我还是想做出来。
这个题的主要麻烦是在查重，就是你得到一个环，必须跟之前去比，环不重复，这个比的过程很麻烦。
可以用自带的set（）方法，如果能定义一下环类的“==”，简易地判断一下两个环是否一样
查询资料
set()去重使用的首先是__hash__计算哈希值相等，然后使用__eq__去看是否相等，详情见下边的博客
https://www.cnblogs.com/linshuhui/p/9580620.html
https://blog.csdn.net/echo666/article/details/108854606
测试Circle类
# coding: utf-8
# 类
class Circle:
def __init__(self,series:list):
self.series = series
def __str__(self):
return self.series.__str__()
def __hash__(self):
return hash(sum(self.series))
def __eq__(self,other):
if type(other) != Circle:
return False
if len(self.series) != len(other.series):
return False
first = self.series[0]
if first not in other.series:
return False
return self.series == other.series[other.series.index(first):] + other.series[:other.series.index(first)]
circle1 = Circle([1,2,3,4,5])
circle2 = Circle([2,4,5,1,3])
circle3 = Circle([4,5,1,2,3])
set1 = set()
set1.add(circle1)
set1.add(circle2)
set1.add(circle3)
for circle in set1:
print(circle)
"""
结果：
[2, 4, 5, 1, 3]
[1, 2, 3, 4, 5]
"""最后代码
# coding: utf-8
# 类
# import sys # 导入sys模块
# sys.setrecursionlimit(3000) # 将默认的递归深度修改为3000
class Circle:
def __init__(self,series:list):
self.series = series
def __str__(self):
return self.series.__str__()
def __hash__(self):
return hash(sum(self.series))
def __eq__(self,other):
if type(other) != Circle:
return False
if len(self.series) != len(other.series):
return False
first = self.series[0]
if first not in other.series:
return False
return self.series == other.series[other.series.index(first):] + other.series[:other.series.index(first)]
# 输入
M = int(input("")) # 模块总数
N = int(input("")) #后续N行
nodes = {}
appear_points = set()
circles = set()
visited = []
for i in range(N):
a,b = [int(i) for i in input("").split(" ")]
if a not in nodes:
nodes[a] = [b]
else:
nodes[a].append(b)
appear_points.add(a)
appear_points.add(b)
# 函数
def dfs(num,start_num):
visited.append(num)
for next_num in nodes[num]:
if next_num not in visited[1:] and next_num in nodes:
if next_num == start_num:
circles.add(Circle(visited.copy()))
# print(visited)
return
dfs(next_num,start_num)
# 回溯
visited.pop()
if num ==start_num: # 最开始的点也需要回溯掉，删除第一个数
visited.pop()
# main
point = 100
point -= M - len(appear_points)
for num in nodes.keys():
result = dfs(num,num)
point -= 2 * len(circles)
print(point)
if circles:
for circle in circles:
print(circle)示例和结果
下边是两个例子
输入和结果分别为
8
6
1 2
2 5
5 1
5 2
5 3
8 2
结果：
93
[1, 2, 5]
[2, 5]
6
7
1 4
1 6
3 1
4 3
4 6
6 1
6 3
结果：
88
[1, 6]
[1, 4, 3]
[3, 1, 6]
[1, 4, 6]
[4, 6, 3, 1]感谢程序，我自己都没有看出来[4 6 3 1]这个环
感觉做出来还是挺有成就感的！
对于__eq__之中，如果不判断一下类对不对，到底会不会导致两个不同的类的实例相等的情况，我做了个实验
# coding: utf-8
# 类
# import sys # 导入sys模块
# sys.setrecursionlimit(3000) # 将默认的递归深度修改为3000
class Circle:
def __init__(self,series:list):
self.series = series
def __str__(self):
return self.series.__str__()
def __hash__(self):
return hash(sum(self.series))
def __eq__(self,other):
# if type(other) != Circle:
# return False
if len(self.series) != len(other.series):
return False
first = self.series[0]
if first not in other.series:
return False
return self.series == other.series[other.series.index(first):] + other.series[:other.series.index(first)]
class Circle1:
def __init__(self,series:list):
self.series = series
def __str__(self):
return self.series.__str__()
def __hash__(self):
return hash(sum(self.series))
def __eq__(self,other):
# if type(other) != Circle:
# return False
if len(self.series) != len(other.series):
return False
first = self.series[0]
if first not in other.series:
return False
return self.series == other.series[other.series.index(first):] + other.series[:other.series.index(first)]
circle1 =Circle([1,2,3])
circle2 =Circle1([1,2,3])
print(circle1 == circle2)
# 结果
# True确实应该判断下。还尝试了在第一个类中有这个判断，第二种没有的情况，结果为False；第一个类没有判断，第二种有判断，结果为True。
这个结果说明“==”使用的是前边那个东西的__eq__函数