HDU1704 Rank POJ3660 Cow Contest（传递闭包）

December 19, 2015

HDU1704 Rank 题目链接

POJ3660 Cow Contest 题目链接

题意：N 个人，M 场比赛，每场比赛第一个数是胜者，胜负关系具有传递性。问这些人不能确定胜负关系有几对。POJ3360 与此题题意相同，只不过改成了求能确定排名的人数（一个人与其他所有人的胜负关系都是确定的情况下就能确定排名）。

给出 HDU1704 的 AC 代码，POJ3360 在此代码稍微修改下即可。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int pic[600][600];
int main(){
    //freopen("a.txt", "r", stdin);
    int t;
    cin >> t;
    while(t--){
        memset(pic, 0, sizeof(pic));
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
            pic[i][i] = 1;
        while(m--){
            int a, b;
            scanf("%d %d", &a, &b);
            pic[a][b] = 1;
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                if(pic[i][k]){
                    for(int j = 1; j <= n; j++){
                        if(pic[k][j])
                            pic[i][j] = 1;
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
        for(int j = i+1; j<= n; j++){
            if(!pic[i][j] && !pic[j][i])
                ans++;
        }
        cout << ans <<endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]