软件模块循环依赖题目题解（一）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# coding: utf-8
# 输入
M = int(input("")) # 模块总数
N = int(input("")) #后续N行
nodes = {}
appear_points = set()
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):
if num not in nodes: # num没有下一个node
return
else:
for next_num in nodes[num]:
if next_num == start_num:
return True
result = dfs(next_num,start_num)
if result:
return True
# main
point = 10
point -= M - len(appear_points)
for num in nodes.keys():
result = dfs(num,num)
if result:
point -= 2
break
print(point)

1
2
3
4
5
6
5
3
0 1
1 2
2 0
结果：6

1
2
3
4
5
6
7
8
6
5
0 1
0 2
1 3
2 4
2 5
结果：10