[bzoj1612][Usaco2008 Jan]Cow Contest奶牛的比赛_dfs

Cow Contest奶牛的比赛 bzoj-1612 Usaco-2008 Jan

题目大意：题目链接。

注释：略。

---

想法：

我们对于每个点dfs，看一下比这个点大的点加上比这个点小的点是否是n-1即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=110;

int n,m,ans;

int f1[N],f2[N];

int G1[N][N],G2[N][N];

bool vis[N];

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

void DFS1(int x)

{

    vis[x]=1;f1[x]++;

    for(int i=1;i<=n;i++)

	{

        if((!G1[x][i])||vis[i]) continue;

        DFS1(i);

    }

}

void DFS2(int x)

{

    vis[x]=1;f2[x]++;

    for(int i=1;i<=n;i++)

	{

        if(!(G2[x][i])||vis[i]) continue;

        DFS2(i);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

	{

        int u,v;

        scanf("%d%d",&u,&v);

        G1[u][v]=1;G2[v][u]=1;

    }

    for(int i=1;i<=n;i++)

	{

        DFS1(i);

        for(int j=1;j<=n;j++) vis[j]=0;

    }

    for(int i=1;i<=n;i++)

	{

        DFS2(i);

        for(int j=1;j<=n;j++) vis[j]=0;

    }

    for(int i=1;i<=n;i++) if(f1[i]+f2[i]-1==n) ans++;

    printf("%d\n",ans);

    return 0;

}

小结：好题。