欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

floyd poj 3660 Cow Contest

程序员文章站 2022-07-04 20:07:01
...

确定排名顺序问题

floyd poj 3660 Cow Contest

dfs : 以每个顶点正向和反向(反向存图)分别遍历一次,就可以求出该顶点的出度和如度之和。满足 D入 + D出 == N-1,就可以确定其排名。参见离散数学。

floyd : relation[i][j] = 1 或者 relation[j][i] = 1 表示 i,j 之间有关系。若某一个顶点与其余 n-1个顶点都有关系的话,其排名是确定的。求任意两个顶点之间是否有关系可以用floyd算法。

注意是有向图

#include <iostream>
#include <memory.h>
using namespace std;
int G[105][105];
int Indegree[105];
int Outdegree[105];
int N,M;
void Floyd()
{
    for( int u = 1; u <= N; u++ )
        for( int v = 1; v <= N; v++ )
            for( int w = 1; w <= N; w++ )
            {
                if( G[v][u] && G[u][w] )
                {
                    G[v][w] = 1;
                }
            }
}
int main()
{
    cin >> N >> M;
    memset(G, 0, sizeof(G));
    memset(Outdegree, 0, sizeof(Outdegree));
    memset(Indegree, 0, sizeof(Indegree));
    while( M-- )
    {
        int Begin,End;
        cin >> Begin >> End;
        G[Begin][End] = 1;
    }
    Floyd();
    for( int i = 1; i <= N; i++ )
        for( int j = 1; j <= N; j++ )
    {
        if( G[i][j] )
        {
        Indegree[j]++;
        Outdegree[i]++;
        }
    }
    int num = 0;
    for( int i = 1; i <= N; i++ )
    {
        if( Indegree[i] + Outdegree[i] == N-1 )
            num++;
    }
    cout << num << endl;
    return 0;
}