POJ 3660 Cow Contest. (傳遞閉包)【Floyd】

<題目連結>

題目大意：

有n頭牛， 給你m對關系（a, b）表示牛a能打敗牛b， 求在給出的這些關系下， 能确定多少牛的排名。

解題分析：

首先，做這道題要明确，什麼叫确定牛的排名。假設該牛被x頭牛打敗(直接或間接)，同時它也有y頭手下敗将(直接或間接)，當x+y=n-1時，即除這頭牛本身外，其他所有的牛都為這頭牛貢獻了出度或者入度。即，當這頭牛與其它所有的牛的輸赢關系都确定時(直接或間接)，這頭牛的排名也就可以确定了。而題目隻給出了一些牛的直接輸赢關系，這時，我們就可以利用Floyed算法，得到牛群之間的間接輸赢關系。

比如：a-->b ,b-->c  ,則 a-->c，這種傳遞關系的思想，在Floyed 的三重循環中可以很輕易的展現，如果不明白就自己畫圖感受一下。

#include <cstdio>
#include <cstring>

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        int line[110][110];         //line[i][j]  表示 i 赢 j 
        memset(line,0,sizeof(line));
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            line[a][b]=1;        //輸入的是能夠直接确定輸赢關系的點 
        }

        /* Floyed -傳遞閉包 */
        
        //即，如果a-->b,b-->c的話，那麼a-->c
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    if(line[j][i]&&line[i][k]){
                        line[j][k]=1;
                    }
                }
            }
        }
        //用Floyed算法将那些間接的輸赢關系也全部計算出來 
        
        int ans=0;
        for(int i=1;i<=n;i++){
            bool flag=true;
            for(int j=1;j<=n;j++){
                if(i==j)continue;
                if(!line[i][j]&&!line[j][i])flag=false;      //如果除它自己以外，還存在不能夠和它确定輸赢的點(直接或間接)，那麼這個點的位置不能夠确定 
            }
            if(flag){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}