大家好，我是爬行系，今天打卡的是洛谷P2853 Cow Picnic S，考查深度优先搜素（bfs)

文章目录

• Cow Picnic S
• • 题目描述
  • 解题思路
  • Ac代码

Cow Picnic S

题目描述

• 题目大概意思就是，有k只奶牛分散在N个牧场，牧场之间有M条有向边，求所有奶牛都可到达的地方．那么，有多少这样的牧场呢？
• 题目链接

解题思路

通过对每个奶牛所在牧场进行深搜遍历，每到达一个牧场，就把第i牧场的count[i]++,等所有奶牛都遍历结束后，只要count[i](i从1到N）的值等于k,就说明该牧场符合规定，ans++,最后输出ans就是答案

Ac代码

import java.util.Scanner;public class Main{static int[] cow;static int[][] edge;static int[] count;static int k,N,M;static int ans;  public static void main(String[] args) {// TODO Auto-generated method stub  Scanner sc=new Scanner(System.in);  k=sc.nextInt();//奶牛的个数  N=sc.nextInt();//牧场的个数  M=sc.nextInt();//N条有向边  cow=new int[k+1];  for(int i=0;i<k;i++) {  cow[i]=sc.nextInt();  }  edge=new int[N+1][N+1];  for(int i=0;i<M;i++) {  int a=sc.nextInt();  int b=sc.nextInt();  edge[a][b]=1;  }  count=new int[N+1];  for(int i=0;i<k;i++) {  int[] vis=new int[N+1];  dfs(vis,cow[i]);  }  for(int i=1;i<=N;i++) {  if(count[i]==k) {  ans++;  }  }  System.out.println(ans);}  private static void dfs(int[] vis,int cow) {  vis[cow]=1;  count[cow]++;  for(int i=1;i<=N;i++) {  if(edge[cow][i]!=0&&vis[i]!=1) {  dfs(vis,i);  }  }  }}

历史新知