Acwing：通信网络（DFS Python）

 题目链接：3250. 通信网络 - AcWing题库

这题第一反应其实是挺简单的 很多算法都可以 dfs，拓扑图，传递闭包都可以

但是如果想AC，两次dfs是比较好的选择。

枚举每一个点，做一次正向dfs和一次反向dfs，分别代表：这个点能到哪些点，哪些点能到这个点，然后这两个集合的全集如果等于N的话，ans+1

其余细节请见注释～

N,M = map(int,input().split())
ans = 0
g1,g2 = dict(),dict() # 这里用邻接表来储存，比邻接矩阵运行快且节省空间

for i in range(M) :
    a,b = map(int,input().split())
    if a not in g1.keys() : # 正向存图
        g1[a] = [b]
    else : g1[a].append(b)
    if b not in g2.keys() : # 反向存图
        g2[b] = [a]
    else : g2[b].append(a)
    
def dfs(node,graph,flag) :
    flag[node] = 1 # 自己一定能到自己
    if node in graph.keys() :
        for key in graph[node] :
            if flag[key] == 0 : dfs(key,graph,flag)
        
for i in range(1,N+1) :
    flag1 = [0 for i in range(N+1)] # 正向能到哪些点
    flag2 = [0 for i in range(N+1)] # 反向能到哪些点
    dfs(i,g1,flag1) 
    dfs(i,g2,flag2)
    tmp = 0
    for i in range(1,N+1) :
        if flag1[i] or flag2[i] : tmp += 1 # 如果正向或者反向可达点i
    if tmp == N : ans += 1 # 如果总数是N，答案+1
    
print(ans)