求出每个点能到达的点。如果有一个点,排名在它之前的和排名在它之后的点之和为n-1,那么它的排名就是确定的。Floyd即可。


题目地址:http://poj.org/problem?id=3660


代码:

Memory: 712 KB
Time: 63 MS
Language: G++
Result: Accepted
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 105
bool omap[MAX][MAX];
int n, m, a, b;
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0;i<m;i++){
            scanf("%d%d", &a, &b);
            omap[a][b] = 1;
        }
        for(int k=1;k<=n;k++){
            for(int u=1;u<=n;u++){
                for(int v=1;v<=n;v++){
                    omap[u][v]=(omap[u][v]||(omap[u][k]&&omap[k][v]));
                }
            }
        }
        int ans=0, cnt;
        for(int u=1;u<=n;u++){
            cnt=0;
            for(int v=1;v<=n;v++){
                if(omap[u][v]||omap[v][u])cnt++;
            }
            if(cnt==n-1)ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}