Pagini recente » Cod sursa (job #889125) | Borderou de evaluare (job #2338739) | Cod sursa (job #2796413)
adj_list = {}
my_list = []
def add_node(node):
if node not in my_list:
my_list.append(node)
def add_edge(node1, node2):
temp = []
if node1 in my_list and node2 in my_list:
if node1 not in adj_list:
temp.append(node2)
adj_list[node1] = temp
elif node1 in adj_list:
temp.extend(adj_list[node1])
temp.append(node2)
adj_list[node1] = temp
def dfs(my_graph, starting_node):
stack, result = [starting_node], []
while stack:
node = stack.pop()
if node in result:
continue
result.append(node)
if node in my_graph:
for n in my_graph[node]:
stack.append(n)
return result
def graph():
for node in adj_list:
print(node, " ---> ", [i for i in adj_list[node]])
def read():
n, m = [int(x) for x in f.readline().split()]
for i in range(1, n + 1):
add_node(i)
for i in range(m):
x, y = [int(z) for z in f.readline().split()]
add_edge(x, y)
add_edge(y, x)
return n, m
visit = []
connected = 0
f = open("dfs.in", "r")
f_out = open("dfs.out", "w")
N, M = read()
for nod in range(1, N + 1):
if nod not in visit:
connected += 1
result_dfs = dfs(adj_list, nod)
for each_node in result_dfs:
visit.append(each_node)
res = dfs(adj_list, 1)
f_out.write(str(connected))