思路:
应该要将题目进行转化,转化为平时可以理解的形式。这里就是说求所有这样的点,其他点要么可以访问他,要么可以被他访问到,也就是说用两种边,一种是正向的,一种是反向的,然后dfs就行了。
代码:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
const int M = 20005;
int h1[N], h2[N], e[M], ne[M], idx;
bool st1[N], st2[N];
int n,m;
void add(int h[], int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int h[], bool st[]){
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){
int v = e[i];
if(!st[v])dfs(v, h, st);
}
}
int main(){
cin>>n>>m;
memset(h1, -1, sizeof(h1));
memset(h2, -1, sizeof(h2));
while(m--){
int a,b;
cin>>a>>b;
add(h1, a, b);
add(h2, b, a);
}
int res = 0;
for(int i = 1;i<=n;i++){
memset(st1, false, sizeof(st1));
memset(st2, false, sizeof(st2));
dfs(i, h1, st1);
dfs(i, h2, st2);
int cnt = 0;
for(int j = 1;j<=n;j++){
if(st1[j] || st2[j]){
cnt++;
}
}
if(cnt == n){
res++;
}
}
cout<<res;
}