1076 Forwards on Weibo (30分)

1076 Forwards on Weibo (30分)

前言：一开始没看懂题目，我英文太差了，呜呜呜呜Wwwww。

题意：给定有向图，求从某一点出发距离不超过$l$的点的个数。

思路：与层数有关的题目用$bfs$更优，用$dfs$类似于跑最短路，统计时需要再遍历一遍。

$bfs$解法：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,l,q,vis[N];
vector<int>e[N];
struct node{
    int u,d;
};
int bfs(int st){
    queue<node>q;
    q.push({st,0}),vis[st]=1;int s=-1;
    while(!q.empty()){
        int u=q.front().u,dis=q.front().d;q.pop();
        printf("u=%d,dis=%d\n",u,dis);
        if(dis>l) return s;
        s++;
        for(int v:e[u]){
            if(!vis[v]) q.push({v,dis+1}),vis[v]=1;
        }
    }return s;
}
int main(){
    scanf("%d%d",&n,&l);
    for(int i=1,k,v;i<=n;i++){
        scanf("%d",&k);
        for(int j=0;j<k;j++) scanf("%d",&v),e[v].pb(i); 
    }
    scanf("%d",&q);
    while(q--){
        int st;scanf("%d",&st);printf("%d\n",bfs(st));mst(vis,0);
    }
    return 0;
}

$dfs$解法:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,l,q,s,vis[N],d[N];
vector<int>e[N];
void dfs(int u,int fa){
    if(d[u]>=l) return;
    for(int v:e[u]){
        if(v==fa) continue;
        if(d[v]>d[u]+1) d[v]=d[u]+1,dfs(v,u); 
    }
}
int main(){
    scanf("%d%d",&n,&l);
    for(int i=1,v;i<=n;i++){
        int k;scanf("%d",&k);
        for(int j=0;j<k;j++){
            scanf("%d",&v),e[v].pb(i);
        } 
    }
    int q;scanf("%d",&q);
    while(q--){
        int st;scanf("%d",&st);mst(d,0x3f),s=d[st]=0,dfs(st,0);
        for(int i=1;i<=n;i++)    if(d[i]<=l) s++;
        printf("%d\n",s-1);
    }
    return 0;
}