题解 P2419 【[USACO08JAN]牛大赛Cow Contest】

Starria的脑残粉

2017-07-13 14:27:51

Solution

正向反向dfs罢了,对每个点都搜出他能到达的所有点(大概是比floyd的复杂度优的吧 懒得挂边表所以用邻接矩阵 于是n^3 ```cpp #include<bits/stdc++.h> using namespace std; int n,m,x,y,a[200][200],ans; bool flag[200]; int dfs1(int d){//正向 int ans=1;flag[d]=true; for (int i=1;i<=n;i++) if (a[d][i]&&!flag[i])ans+=dfs1(i);//计数 return ans; } int dfs2(int d){//反向 int ans=1;flag[d]=true; for (int i=1;i<=n;i++) if (a[i][d]&&!flag[i])ans+=dfs2(i); return ans; } int main(){ ios::sync_with_stdio(false); cin>>n>>m;for (int i=1;i<=m;i++)cin>>x>>y,a[x][y]=1; for (int i=1;i<=n;i++){ memset(flag,false,sizeof(flag)); if (dfs1(i)+dfs2(i)-1==n)ans++;//比当前数大的和比当前数小的加起来=n时可以确定当前的排名 } cout<<ans<<endl;//输出统计出的个数 } ```