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

2017-07-13 14:27:51


正向反向dfs罢了,对每个点都搜出他能到达的所有点(大概是比floyd的复杂度优的吧

懒得挂边表所以用邻接矩阵

于是n^3

#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;//输出统计出的个数
}