Pagini recente » Cod sursa (job #1439152) | Cod sursa (job #1365391) | Cod sursa (job #2531979) | Cod sursa (job #1634235) | Cod sursa (job #3164152)
def dfs(nod):
viz[nod - 1] = 1
for next in g[nod - 1]:
if viz[next - 1] == 0:
dfs(next)
stiva.append(nod)
def dfs_t(nod):
scc.append(nod)
viz[nod - 1] = 1
for next in gt[nod - 1]:
if viz[next - 1] == 0:
dfs_t(next)
linie = input().strip().split()
n, m = int(linie[0]), int(linie[1])
g = [[] for _ in range(n)]
gt = [[] for _ in range(n)]
viz = [0] * n
stiva = []
ctc = []
for i in range(m):
linie = input().strip().split()
x, y = int(linie[0]), int(linie[1])
g[x - 1].append(y)
gt[y - 1].append(x)
for i in range(1, n + 1):
if viz[i - 1] == 0:
dfs(i)
viz = [0] * n
while stiva:
x = stiva.pop()
if viz[x - 1] == 0:
scc = []
dfs_t(x)
ctc.append(scc)
print(len(ctc))
#count = 0
#for comp in ctc:
# count += 1
# for el in comp:
# print(count, end=" ")