原题链接

这里是原题嗷

思路

求有向图中，可达以及可被达点集合是全集的点个数。判断可达性的方法有很多，例如bfs, dfs，也可以通过拓扑排序（无环图中），乃至缩点等方式。此处实现使用bfs。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

const int N= 1000 +10;
const int M = 10000 +10;
int tot;
int head[N], ver[M], Next[M];
bitset<N> vis[N];
bool bvis[N];

vector<pair<int,int>> edges;

void Init(){
    tot = 0;
    memset(head, 0, sizeof head);
    memset(ver, 0, sizeof ver);
    memset(Next, 0, sizeof Next);
}

void Add(int x, int y){
    ver[++tot] = y, Next[tot] = head[x];
    head[x] = tot;
}

void bfs(int x){
    memset(bvis, 0, sizeof bvis);
    queue<int> q;
    q.push(x);
    vis[x][x] = 1;
    bvis[x] = true;
    while(q.size()){
        int cur = q.front();q.pop();
        for(int i = head[cur];i;i = Next[i]){
            if(bvis[ver[i]])continue;
            vis[x][ver[i]] = 1;
            bvis[ver[i]] = true;
            q.push(ver[i]);
        }
    }
}


int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        edges.push_back(pair(x, y));
    }
    
    Init();
    for(int i=0;i<N;i++)vis[i].reset();
    
    for(int i=0;i<m;i++){
        Add(edges[i].first, edges[i].second);
    }
    
    for(int i=1;i<=n;i++){
        bfs(i);
    }
    
    Init();
    for(int i=0;i<m;i++){
        Add(edges[i].second, edges[i].first);
    }
    
    int ans=0;
    for(int i=1;i<=n;i++){
        bfs(i);
        if(vis[i].count()==n)ans++;
    }
    
    cout<<ans<<endl;
    return 0;
}