传送门：https://www.luogu.org/problemnew/show/P2419
这道题拿到之后想了很多种做法，贪心。。。。以及建树。。。然后。。。。从入度为零的点求最短路。。。。然鹅好像不行。。。。
这道题可以拿floyd做qww。又是一道考验大家是否理解Floyd的题。
floyed不仅能求任意两点的最短路，还能求一个点能否到另一个点。
这道题用了floyed算法的变化，用floyed算法判图的连通性，用f[i][j]判断从i到j联不联通。
f[i][j]=f[i][j]||(f[i][k]&&f[k][j])表示i到j联不联通，要么一开始i能到j,要么i能到k，k再能到j。
用floyed求出每个点与这个点的关系，只要这个点和其他n-1个点的关系都确定了，就能确定他的排名。
#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 105
using namespace std;
inline int read() {
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
int a,b,n,m,f[N][N];
void init(){
n = read(),m = read();
for(int i = 1;i <= m;i++){
a = read(),b = read();
f[a][b] = 1;
}
return ;
}
void floyd(){
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++){
f[i][j] = f[i][j] || f[i][k] && f[k][j];
}
return ;
}
int ans;
void solve(){
for(int i = 1;i <= n;i++){
int sum = 1;
for(int j = 1;j <= n;j++)
if(i == j) continue;
else
sum = sum && (f[i][j] || f[j][i]);
ans += sum;
}
printf("%d
",ans);
return ;
}
int main(){
init();
floyd();
solve();
return 0;
}