题目链接
题目大意：给定m次比赛的结果,询问能够确定名次的人数
题解：可以建立正反图跑dfs……直接暴力传递floyd算就行了……i能确定名次=i和其他n-1头牛联通(关系已知)
我的收获：水水水
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,x,y,tot;
int w[
1005][
1005];
void floyed()
{
for(
int k=
1;k<=n;k++)
for(
int i=
1;i<=n;i++)
for(
int j=
1;j<=n;j++)
w[i][j]|=w[i][k]&w[k][j];
}
void pd(
int x)
{
int tmp=
0;
for(
int y=
1;y<=n;y++)
if(w[x][y]||w[y][x]) tmp++;
if(tmp==n-
1) tot++;
}
void init()
{
cin>>n>>m;
memset(w,
0,
sizeof(w));
for(
int i=
1;i<=m;i++)
{
scanf(
"%d%d",&x,&y);
w[x][y]=
1;
}
}
void work()
{
floyed();
for(
int i=
1;i<=n;i++)
pd(i);
printf(
"%d\n",tot);
}
int main()
{
init();
work();
return 0;
}
