可以使用邻接矩阵或邻接表
步骤:
模板题1:P4017 最大食物链计数
#include<bits/stdc++.h>
using namespace std;
const int N=5000005,M=80112002;
queue<int> q;
int n,m,head[N],cnt,d[N],f[N],D[N];
struct Edge{
int nxt,to;
}g[N*2];
void add(int from,int to){
g[++cnt].nxt=head[from];
g[cnt].to=to;
head[from]=cnt;
}
void init(){
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++){
cin>>x>>y; add(x,y); d[y]++; D[x]++;
}
}
void work(){
for(int i=1;i<=n;i++){
if(d[i]==0){
q.push(i); f[i]=1;
}
}
int ans=0;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=head[x];i;i=g[i].nxt){
int v=g[i].to;
d[v]--; f[v]=(f[v]+f[x])%M;
if(d[v]==0) q.push(v);
}
}
for(int i=1;i<=n;i++){
if(!D[i]) ans=(ans+f[i])%M;
}
cout<<ans<<endl;
}
int main(){
init();
work();
return 0;
}
|