PAT (Advanced Level) Practice 1076 Forwards on Weibo

约定不等于承诺〃 2023-06-27 04:23 14阅读 0赞

BFS遍历+记录layer，比较简单...

#include <iostream>
    #include <stdio.h>
    #include <queue>
    #define maxn 1010
    using namespace std;
    int MAP[maxn][maxn] = {0};
    bool visited[maxn];
    int n,l,k;
    void initVisited(){
        for(int i=1;i<=n;i++)
            visited[i] = false;
    }
    struct Node{
        int num;
        int layer;
        Node(){
        }
        Node(int n,int l){
            num = n;
            layer = l;
        }
    };
    void TravelBFS(int root,int &num){
        queue<Node> q;
        visited[root] = true;
        int layer = 0;
        q.push(Node(root,layer));
        while(!q.empty()){
            Node node = q.front();
            q.pop();
            for(int i=1;i<=n;i++){
                if(MAP[node.num][i]!=0 && visited[i]==false){
                    visited[i] = true;
                    num++;
                    q.push(Node(i,node.layer+1));
                }
            }
            if(q.front().layer == l){
                break;
            }
        }
    }
    
    int main()
    {
        scanf("%d%d",&n,&l);
        for(int i=1;i<=n;i++){
            int s;
            scanf("%d",&s);
            for(int j=0;j<s;j++){
                int v;
                scanf("%d",&v);
                MAP[v][i] = 1;
            }
        }
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            int num,root;
            scanf("%d",&root);
            num = 0;
            initVisited();
            TravelBFS(root,num);
            printf("%d\n",num);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关【PAT A1076】Forwards on Weibo

> Weibo is known as the Chinese version of Twitter. One user on Weibo may have many foll

阳光穿透心脏的1/2处/ 2023年07月04日 15:36/ 0 赞/ 25 阅读

相关 PAT (Advanced Level) Practice 1107 Social Clusters

解题方法：并查集。把爱好当成并查集元素。对于每个人当爱好只有一个时，不做任何操作。当爱好大于一个时，两两进行并查集的合并操作。遍历完后，就可找出，每

傷城~/ 2023年07月03日 03:22/ 0 赞/ 60 阅读

相关 PAT (Advanced Level) Practice 1029 Median

输入不要用cin，用scanf，不然会超时。真的要吐血了，没想到是这个点...... 使用cin输入数据时最后一个测试点超时，使用scanf直接89ms过，题限是200ms

今天药忘吃喽~/ 2023年07月02日 05:25/ 0 赞/ 65 阅读

相关 PAT (Advanced Level) Practice 1076 Forwards on Weibo

BFS遍历+记录layer，比较简单... include <iostream> include <stdio.h> include <queue>

约定不等于承诺〃/ 2023年06月27日 04:23/ 0 赞/ 15 阅读

相关 PAT1076 Forwards on Weibo BFS+图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

布满荆棘的人生/ 2023年02月25日 07:10/ 0 赞/ 142 阅读

相关【PAT (Advanced Level) Practice】1124 Raffle for Weibo Followers (20 分)

1124 Raffle for Weibo Followers (20 分) John got a full mark on PAT. He was so happy th

秒速五厘米/ 2022年10月19日 04:18/ 0 赞/ 227 阅读

相关【PAT (Advanced Level) Practice】PAT (Advanced Level) Practice

1006 Sign In and Sign Out (25 分) At the beginning of every day, the first person who s

川长思鸟来/ 2022年10月12日 01:40/ 0 赞/ 65 阅读

相关 1076. Forwards on Weibo (30)

所有的测试点通过，除了最后一个运行超时 \include<iostream> using namespace std; \define max 10005 int

短命女/ 2022年08月13日 09:29/ 0 赞/ 169 阅读

相关 1076. Forwards on Weibo (30)

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many follow

怼烎@/ 2022年05月30日 02:11/ 0 赞/ 173 阅读

相关 PAT (Advanced Level) Practice（更新中）

Source: > [PAT (Advanced Level) Practice][PAT _Advanced Level_ Practice] Reference:

超、凢脫俗/ 2021年12月20日 06:31/ 0 赞/ 247 阅读