传送门
解题思路
传递闭包板子题。
直接建边然后Floyd即可。
最后对于每一个点，若比他小的(ma[i][j])加上比他大的(ma[j][i])等于n-1，则他可以确定排名。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ma[105][105],ans;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
ma[u][v]=1;
}
for(int i=1;i<=n;i++) ma[i][i]=1;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
ma[i][j]|=ma[i][k]&ma[k][j];
}
}
}
for(int i=1;i<=n;i++){
int res=0;
for(int j=1;j<=n;j++){
res+=ma[i][j]+ma[j][i];
}
if(res-2==n-1) ans++;
}
cout<<ans;
return 0;
}