Cod sursa(job #2308004)

Utilizator Raoul_16Raoul Bocancea Raoul_16 Data 26 decembrie 2018 01:00:31
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.77 kb
def main():

	def DFS(Node, Graph, use):
		use[Node] = True
		for neighbour in Graph[Node]:
			if not use[neighbour]:
				DFS(neighbour, Graph, use)

	def read():
		for i in range(M):
			x = int(lines[i + 1].replace('\n', ' ').split(' ')[0])
			y = int(lines[i + 1].replace('\n', ' ').split(' ')[1])
	 
			Graph[x].append(y)
			Graph[y].append(x)
	 
	f = open("dfs.in", 'r')
	g = open('dfs.out', 'w+')

	lines = f.readlines()



	N = int(lines[0].replace('\n', ' ').split(' ')[0])
	M = int(lines[0].replace('\n', ' ').split(' ')[1])
	 
	Graph = {}
	use = {}

	for i in range(1, N + 1):
		Graph[i] = [];
		use[i] = False;
	 
	read()
	 
	counter = 0
	for i in range(1, N + 1):
		if not use[i]:
			DFS(i, Graph, use)
			counter += 1
	 
	g.write(str(counter))

if __name__ == '__main__':
	main()