2021.11.14/dfs/通信网络
https://www.acwing.com/problem/content/description/3253/
因为点的个数只有1000，故可以对每一个点进行dfs

时间复杂度 N*M

由题意我们可以得知，对于一条路径，路径头部和路径尾部都可以知道路径上的所有点

所以我们将一条边分两次储存，一次储存正向边（对于头部点），一次储存反向边（对于尾部点）

对于路径 ： 1 -> 2 -> 4 -> 5
正向查找时 1 可以找到4个点（包括自己）
反向查找时 5 可以找到4个点（包括自己）

问：为什么正向和反向不能一起混合查找呢？
答：那和无向边有区别吗？

故本题的思路就是对1-n每一个点进行两次dfs，存储可以到达的点（用st）可以开1000 * 1000的大小
如果每个点均可到达，则该点满足要求

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 10010;

bitset<N> st[N], st2[N];//这里我用bitset方便位运算，相对只占1/8的空间
int ver[M], nxt[M], head[N], tot;//邻接表
int ver2[M], nxt2[M], head2[N], tot2;//duoble
int n, m, x, y, ans;

inline void add(int x, int y){ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;}//正向边
inline void add2(int x, int y){ver2[++tot2] = y, nxt2[tot2] = head2[x], head2[x] = tot2;}//反向边

void dfs(int u, int x){//正向搜索
    st[u][x] = 1;
    for(int i = head[x], y; i; i = nxt[i])
        if(!st[u][y = ver[i]]) dfs(u, y);
}
void dfs2(int u, int x){//反向搜索
    st2[u][x] = 1;
    for(int i = head2[x], y; i; i = nxt2[i])
        if(!st2[u][y = ver2[i]]) dfs2(u, y);
}
int main(){
    cin >> n >> m;//输入大小
    for(int i = 0; i < m; i++) {cin >> x >> y; add(x, y), add2(y, x);}//输入边
    for(int i = 1; i <= n; i++) dfs(i, i), dfs2(i, i);//搜索
    for(int i = 1; i <= n; i++) ans += ((st[i] | st2[i]).count() == n);//累加答案
    cout << ans;//输出答案
    return 0;
}
//(st[i] | st2[i]) 是将两个bitset取交集，正向可以达到或者反向可以达到都行
//count 是bitset自带的函数，返回其中二进制 1 的个数