首页技术正文

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

程序员山山技术 2022年11月23日

0 收藏 887 点赞 4,171 浏览 985 个字

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;
}