这是一个难度适中的紫题

· · 题解

传送门

这是个有向图，还有环，很难搞。

但是我们发现，有环不一定答案就是'inf'，因为那个环可能到不了终点……别问我怎么知道

所以在这之前，我们设

为了更新p数组，我们先要从点2倒着走一遍。

判环：一次递归中如果重复走了一个点，那么就有环。

除去有环的情况后，我们发现这就是一个类似于树的东西（只不过一个点可能有多个爸爸）

于是我们求考虑一下树形DP。

我们设：

显然

f_i=\Sigma f_{son_{i}}

然后初值就是-1，f_2=1

我感jio我讲的不是很清楚，但是代码里有注释：

#include<cstdio>
#include<cstring>
#define inf 1000000000
#define N 10010
struct edge
{
    int to,next;
}t[10*N],T[10*N];
int n,m,head[N],last[N],cnt,f[N];
bool b[N],p[N],Inf;
void add(int x,int y)
{
    t[++cnt]=(edge){y,head[x]};//图正着存一遍
    head[x]=cnt;
    T[cnt]=(edge){x,head[y]};//又倒着存一遍 
    last[y]=cnt;
}
void tree(int k)//正着搜，更新答案 
{
    f[k]=0;//必须的，因为我们的初值-1 
    for (int i=head[k];i;i=t[i].next)
    {
        if (Inf) return;
        if (!b[t[i].to])//下一个点没走过 
        {
            b[t[i].to]=1;
            if (f[t[i].to]==-1) tree(t[i].to);//有点记忆化的感jio 
            f[k]+=f[t[i].to],f[k]%=inf;
            b[t[i].to]=0;
        }
        else if (p[t[i].to])//如果走过，就证明遇到了环，但我们还要判断这个环能不能到达2好点 
        {
            puts("inf");
            Inf=1;//标记一下 
            return;
        }
    }
}
void go(int k)//倒着跑，从2号点搜回去，更新p数组 
{
    for (int i=last[k];i;i=T[i].next)
    if (!b[T[i].to])
    {
        b[T[i].to]=1;
        p[T[i].to]|=p[k];
        go(T[i].to);
    }
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d%d",&n,&m);
    for (int x,y;m--;) scanf("%d%d",&x,&y),add(x,y);
    f[2]=p[2]=b[2]=1;
    go(2);
    memset(b,0,sizeof b);//别忘更新 
    b[1]=1;
    tree(1);
    if (Inf) return 0;
    printf("%d",f[1]);
    return 0;
}