Improve SPAM（两次dfs或者bfs+拓扑排序）

先给出两个数，有n个点，其中1-m点是发送邮件点，然后有m行，第i行的第一个数，代表着第i个发送邮件点能够发送的地址。
可以用两个dfs跑出来，或者用bfs预处理，再跑一遍拓扑
dfs:

#include<stdio.h>
#include<iostream>
#include<vector>
#include<memory.h>
#include<queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
int n,m;
const int maxn=2e3+20;
const int mod=1e9+7;
queue<int>x;
bool vis[maxn];
ll f[maxn];
vector<int> G[maxn];
ll dfs1(int u)//跑到大于m时直接返回f值
{
    if(f[u])
    return f[u];
    for(int i=0;i<G[u].size();++i)
    {
        f[u]=(f[u]+dfs1(G[u][i]))%mod;
    }
    return f[u];
}
ll dfs2(int u)//既要满足点大于m又要满足该点只访问一次
{
    if(u>m)
    return 1;
    ll ans=0;
    for(int i=0;i<G[u].size();++i)
    {
        if(!vis[G[u][i]])
        {
            vis[G[u][i]]=1;
            ans=(ans+dfs2(G[u][i]))%mod;
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int k;
        cin>>k;
        while(k--)
        {
            int x;
            cin>>x;
            G[i].push_back(x);
        }
    }
    for(int i=m+1;i<=n;++i)
    f[i]=1;
    ll ans1=dfs1(1);
    ll ans2=dfs2(1);
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

bfs+拓扑

#include<stdio.h>
#include<iostream>
#include<vector>
#include<memory.h>
#include<queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
int n,m;
ll ans1,ans2;
const int maxn=2e3+20;
const int mod=1e9+7;
bool via[maxn];
int ci[maxn];
int in[maxn];
ll f[maxn];
int head[maxn];
int cnt;
vector<int> G[maxn];
struct node
{
    int to,next1;
}e[maxn*maxn];
void addage(int u,int v)//新建图
{
    e[cnt].to=v;
    e[cnt].next1=head[u];
    head[u]=cnt++;
    in[v]++;
}
void bfs()//第一遍bfs处理求出能够到达大于m的邮件，而且该邮件只能到达一次，到达一次后就入队，并且在bfs预处理时建图
{
    ans2 = 0;
    memset(via,0,sizeof(via));
    queue <int> Q;
    Q.push(1);
    via[1] = 1;
    while (!Q.empty()) {
        int t=Q.front();Q.pop();
        if(t>m) 
        ans2++;
        for(int i=0;i<G[t].size();i++ ) 
        {
            int x=G[t][i];
            addage(t,x); 
            if(via[x]==0) 
            {
                via[x] = 1;
                Q.push(x);
            }
        }

    }
}
void topu()
{
    mem(ci,0);
    queue<int>que;
    que.push(1);
    ci[1]=1;
    while(!que.empty())
    {
        int t=que.front();
        que.pop();
        for(int i=head[t];i!=-1;i=e[i].next1)//链式前向星
        {
            int to=e[i].to;
            ci[to]=(ci[to]+ci[t])%mod;//到t点就会再到to点
            in[to]--;
            if(!in[to])
            que.push(to);
        }
    }
    ans1=0;
    for(int i=m+1;i<=n;++i)
    ans1=(ans1+ci[i])%mod;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    mem(head,-1);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;++j)
        {
            int x;
            cin>>x;
            G[i].push_back(x);
        }
    }
    bfs();
    topu();
    cout<<ans1<<" "<<ans2<<endl;
}

本文地址：https://blog.csdn.net/sdtbu_jk19/article/details/109644073