poj 3660(floyd 变形)

题意：

有N头牛，每头牛都会有比他强的或者弱的牛，按照牛的强弱排序，问有几头牛的位置是确定的。

5 5（n,m）
4 3
4 2
3 2
1 2
2 5
则4>3>2>5 && 1>2>5故只有2,5是确定的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define MAXN 102
 8 #define MAXM 4510
 9 
10 int map[MAXN][MAXN];
11 int N,M;
12 int relat[MAXN][MAXN];//0表示i,j的关系未确定，1表示i<j,2表示i>j。
13 
14 void floyd()
15 {
16     for(int k=1;k<=N;k++)
17         for(int i=1;i<=N;i++)
18             for(int j=1;j<=N;j++)
19             {
20                 if(relat[i][j] != 0 || !relat[i][k] || !relat[k][j])
21                     continue;
22                 if(relat[i][k]==2 && relat[k][j]==2)
23                 {
24                     relat[i][j]=2;
25                     relat[j][i]=1;
26                 }
27                 else if(relat[i][k]==1 && relat[k][j]==1)
28                 {
29                     relat[i][j]=1;
30                     relat[j][i]=2;
31                 }
32             }
33 }
34 
35 void solve()
36 {
37     floyd();
38     int ans=0;
39     for(int i=1;i<=N;i++)
40     {
41         bool flag=0;
42         for(int j=1;j<=N;j++)
43         {
44             if(i==j)
45                 continue;
46             if(relat[i][j]==0)
47             {
48                 flag=1;
49                 break;
50             }
51         }
52         if(!flag)
53             ans++;
54     }
55     printf("%d\n",ans);
56 }
57 
58 int main()
59 {
60     int x,y;
61     while(scanf("%d%d",&N,&M) != EOF)
62     {
63         memset(relat,0,sizeof(relat));
64         while(M--)
65         {
66             scanf("%d%d",&x,&y);
67             map[x][y]=1;
68             relat[x][y]=2;
69             relat[y][x]=1;
70         }
71         solve();
72     }
73     return 0;
74 }