题意:
有N头牛,每头牛都会有比他强的或者弱的牛,按照牛的强弱排序,问有几头牛的位置是确定的。
5 5(n,m)4 34 23 21 22 5 则4>3>2>5 && 1>2>5故只有2,5是确定的。
1 #include2 #include 3 #include 4 #include 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。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 }