传递闭包经典应用
奶牛的名次能确定当且仅当在它前面的牛数+在他后面的牛数==n-1
在他前面和后面的牛数可以转化成求完传递闭包后的出度和入度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n,m,dis[105][105],in[105],out[105],cnt;
int main(){
while(cin>>n>>m){
for(int i=1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
dis[u][v]=1;
}
for(int k=1;k<=n;k++){
for(int j=1;j<=n;j++){
for(int i=1;i<=n;i++){
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]) in[j]++,out[i]++;
}
}
for(int i=1;i<=n;i++){
if(in[i]+out[i]==n-1) cnt++;
}
cout<<cnt<<endl;
}
}