Cod sursa(job #2308177)

Utilizator Raoul_16Raoul Bocancea Raoul_16 Data 26 decembrie 2018 15:12:35
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.86 kb
def main():
	try:
		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))
		
	except:
		print('An issue has occured!')
		quit()

if __name__ == '__main__':
	main()