DAG+DP
f[i]表示方案数，于是可以从i的所有儿子转移来。
方便起见我加的是反边。
#include<cstdio> #include<queue> #define N 100005 #define M 200005 using namespace std; queue<int> q; int n, m; struct edge{int next,to;}e[M]; int last[N], f[N], ecnt=0, d[N]; bool out[N], in[N]; void add(int a, int b) { e[++ecnt]=(edge){last[a],b}; last[a]=ecnt; } int main() { scanf("%d%d",&n,&m); for(int i = 1, a, b; i <= m; i++) { scanf("%d%d",&a,&b); add(b,a); out[b]=in[a]=1; d[a]++; } for(int i = 1; i <= n; i++) if(!in[i]) { q.push(i); f[i]=1; } while(!q.empty()) { int x=q.front();q.pop(); for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; f[y]+=f[x]; d[y]--; if(!d[y]) q.push(y); } } int ans=0; for(int i = 1; i <= n; i++) if(in[i] && !out[i]) ans+=f[i]; printf("%d\n",ans); }