牛客每日一题：食物链计数（Java）

食物链计数题意题目的意思大致是给一个图求从一个无入度的起点到无出度的终点的不同路径的数量。思路这道题是很明显的拓扑排序题目也就是每一次找到入度为 0 的点遍历它的路径主要要运用队列这一结构。需要注意的是一个单独的点是不能构成这道题的路径的。正解代码import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { final int N 100005; Scanner in new Scanner(System.in); int n in.nextInt(), m in.nextInt(); ListInteger[] e new List[N]; int []b new int[N]; int []d new int[N]; int []now new int[N]; int []bb new int[N]; for(int i 1;in;i) { e[i] new ArrayList(); b[i] 0; d[i] 0; now[i] 0; bb[i] 0; } for(int i1;im;i){ int u in.nextInt(), v in.nextInt(); add(e,v,u); b[u]; bb[u]; d[v]; } QueueInteger q new ArrayDeque(); int ans 0; for(int i1;in;i) if(b[i] 0){ q.offer(i); now[i] 1; } while(!q.isEmpty()){ int tmp q.peek(); q.poll(); for(int i:e[tmp]){ now[i] now[tmp]; b[i]--; if(b[i] 0) q.offer(i); } } for(int i1;in;i) if(d[i] 0 bb[i] ! 0) ans now[i]; System.out.println(ans); } public static void add(List e[], int x, int y){ e[x].add(y); } }