BZOJ 4562: [Haoi2016]食物链（拓扑排序）

题面：

　　https://www.lydsy.com/JudgeOnline/problem.php?id=4562

　　一句话题意：给一个DAG，求有多少条不完全相同的链，使链首入度为0，链尾出度为0。

题解：

　　将每个入度为零的点权值为一，然后在拓扑排序的过程中将自身的权值加到出边所连的点，然后清空自身。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=100010;
int vis[maxn],dp[maxn],ans,n,m,ru[maxn],cnt,head[maxn];

struct ed{
    int next,to;    
}e[maxn<<2];

void add(int u,int v){
    e[++cnt]=(ed){head[u],v},head[u]=cnt;
}

void bfs(){
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(!ru[i])
            q.push(i),dp[i]=1;
    while(!q.empty()){
        int now=q.front();
        q.pop();vis[now]=0;
        for(int i=head[now];i;i=e[i].next){
            int tt=e[i].to;
            dp[tt]+=dp[now];
            if(!vis[tt])
                q.push(tt),vis[tt]=1;    
        }
        if(head[now])
            dp[now]=0;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&u,&v),add(u,v),ru[v]++;
    bfs();
    for(int i=1;i<=n;i++)    
        if(!head[i]&&ru[i])
            ans+=dp[i];
    printf("%d",ans);
    return 0;    
}