Pagini recente » Cod sursa (job #1664115) | Cod sursa (job #1891409) | Cod sursa (job #1249639) | Cod sursa (job #1606226) | Cod sursa (job #2606364)
import math
import queue
def input_gen_int(fnmae):
with open(fnmae, 'rt') as fin:
for line in fin:
for val in line.split():
yield int(val)
class Graph:
n = 0
m = 0
adj_list = []
def __init__(self, ig):
self.n, self.m = next(ig), next(ig)
self.adj_list = [[] for _ in range(self.n + 1)]
for _ in range(self.m):
f, g = next(ig), next(ig)
self.adj_list[f].append(g)
self.adj_list[g].append(f)
def num_conn_comp(self):
seen = [0 for _ in range(self.n + 1)]
k = 0
for i in range(1, self.n + 1):
if seen[i] == 0:
k += 1
self.dfs(i, seen)
return k
def dfs(self, k, seen):
if seen[k] == 1:
return
seen[k] = 1
for i in self.adj_list[k]:
self.dfs(i, seen)
if __name__ == "__main__":
ig = input_gen_int("dfs.in")
graph = Graph(ig)
with open("dfs.out", 'wt') as fout:
fout.write('{} '.format(graph.num_conn_comp()))