H - Cow Contest POJ - 3660
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int inf = 0x3f3f3f; const int maxn = 110; int mp[maxn][maxn]; int c[maxn]; int r[maxn]; int n, m; void floyd() { for(int k = 1;k<= n;k++)// 求传递闭包 { for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(mp[i][k]&&mp[k][j])mp[i][j] = 1; } } } for(int i = 1;i <= n;i++)// 求出度 和入度 { for(int j = 1;j <= n;j++) { if(mp[i][j]) { mp[i][0]++;// 0 存出度 mp[j][101]++;// 101 存入读 } } } } int main() { ios_base::sync_with_stdio(false); cin>>n>>m; memset(mp, 0, sizeof(mp)); memset(c, 0, sizeof(c)); memset(r, 0, sizeof(r)); for(int i = 0;i < m;i++) { int u, v; cin>>u>>v; mp[u][v] = 1; } floyd(); int ans = 0; for(int i = 1;i <= n;i++) { if(mp[i][0]+mp[i][101] == n-1)ans++;//如果 出度+入读 == 点的个数-1 就能确定其排名 } cout<<ans; return 0; }