Forwards on Weibo (30)

//注意图要反着建
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<vector<int>> follow;
bool visited[1000];
void BFS(int member,int level,int cnt){
    for(int i = 0;i<cnt;i++){
        visited[i]=false;
    }
    queue<int> q;
    q.push(member);
    int l = 0,n=0;
    int leftcnt=1,curcnt=0;
    while(!q.empty()&&l<=level){
        int f = q.front();
        if (!visited[f-1]){
        for(int j = 0;j<follow[f-1].size();j++){
                    q.push(follow[f-1][j]);
                    curcnt++;
                }
        }
        visited[f-1]=true;
        q.pop();
        leftcnt--;
        if(leftcnt ==0){
            leftcnt = curcnt;
            curcnt = 0;
            l++;
        }
    }
    for(int i= 0;i<cnt;i++){
        if(visited[i])
            n++;
    }
    cout<<n-1;
}
int main(){
    int N,L; //N用户总数 L层数
    cin>>N>>L;
    follow.resize(N);
    for(int i=0;i<N;i++){
        int f,t;  //读入的followed by user
        cin>>f;
        for(int j=0;j<f;j++ ){
            cin>>t;
            follow[t-1].push_back(i+1);
        }
    }
     int kn;
    cin>>kn;
    for(int i=0;i<kn;i++){
        int t = 0;
        cin>>t;
        BFS(t,L,N);
        if(i!=kn-1)
            cout<<endl;
    }
}

//weibo graph search
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
//numbered from 1 to N
int n,l;
vector<vector<int> > relation(1010);
bool vis[1010]={0};
int level=0;int follower=0;
void bfs(int start){
	queue<int> list;
	int q=start;
	int levCnt=relation[q].size();
	vis[q]=1;for(int i=0;i<relation[q].size();i++)list.push(relation[q][i]);//this place has one round
	while(!list.empty()){
		if(levCnt==0){
			level++;
			levCnt=list.size();//new round
		}
		if(vis[list.front()]){
			list.pop();
			levCnt--;
			continue;
		}
		q=list.front();vis[q]=1;
		if(level>l-1)return;
		follower++;
		for(int i=0;i<relation[q].size();i++)list.push(relation[q][i]);
		list.pop();levCnt--;
	}
}

int main(){
	cin>>n>>l;
	int temp,temp2;
	vector<int> query;
//	cout<<"size of relation is "<<relation[0].size()<<endl;
	for(int i=1;i<=n;i++){
		cin>>temp;
		for(int j=0;j<temp;j++){
			cin>>temp2;relation[temp2].push_back(i);//graph with direction
		}
	}
	cin>>temp;
	for(int i=0;i<temp;i++){
		cin>>temp2;query.push_back(temp2);
	}
	for(int i=0;i<query.size();i++){
		level=0;follower=0;for(int j=0;j<1010;j++)vis[j]=0;
		bfs(query[i]);
		cout<<follower;if(i!=query.size()-1)cout<<endl;
	}
	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 1005
#define _INF 10000009

int N, L;
int M[MAX], ul[MAX][MAX];
int K, q[MAX];

bool visited[MAX]; queue<int> Q;
int d[MAX][MAX];

int BFScnt(int i, int l) {
	fill(visited, visited + N + 10, false);
	int j; int cnt = 0;
	visited[i] = true; Q.push(i);
	while (!Q.empty()) {
		j = Q.front(); Q.pop(); visited[j] = true;
		for (int w = 1; w <= N; ++w) {
			if (!visited[w] && ul[j][w] > 0 && d[i][w] <= l) {
				cnt++; visited[w] = true; Q.push(w);
			}
		}
	}
	return cnt;
}
void BFSdist(int i) {
	fill(visited, visited + N + 10, false);
	int j; d[i][i] = 0;
	visited[i] = true; Q.push(i);
	while (!Q.empty()) {
		j = Q.front(); Q.pop(); visited[j] = true;
		for (int w = 1; w <= N; ++w) {
			if (!visited[w] && ul[j][w] > 0) {
				d[i][w] = d[i][j] + 1;
				visited[w] = true; Q.push(w);
			}
		}
	}
}

; int main()
{
	cin >> N >> L; int tmp;
	for (int i = 1; i <= N; ++i) {
		fill(ul[i], ul[i] + N + 10, 0);
		fill(d[i], d[i] + N + 10, 0);
	}
	for (int i = 1; i <= N; ++i) {
		cin >> M[i];
		for (int j = 0; j < M[i]; ++j) {
			cin >> tmp;
			ul[tmp][i] = 1;
		}
	}
	cin >> K;
	for (int i = 1; i <= K; ++i)cin >> q[i];


	for (int i = 1; i <= K; ++i) {
		BFSdist(q[i]);
		cout << BFScnt(q[i], L) << endl;
	}


	return 0;
}

#include<cstdio>
#include<queue>
#include<vector>
#include<memory.h>
#define MAX_N 1010
using namespace std;
int n, l;
vector<int> g[MAX_N];
int vertex_level[MAX_N];
bool visited[MAX_N];
int bfs(int node)
{
	memset(vertex_level, 0, MAX_N);
	memset(visited, false, MAX_N);
	queue<int> trav;
	trav.push(node);
	int count = 0;
	visited[node] = true;
	while (!trav.empty() && vertex_level[trav.front()] < l)
	{
		int f = trav.front();
		trav.pop();
		for (int i = 0; i < g[f].size(); ++i)
		{
			if (!visited[g[f][i]])
			{
				visited[g[f][i]] = true;
				vertex_level[g[f][i]] = vertex_level[f] + 1;
				trav.push(g[f][i]);
				++count;
			}
		}
	}
	return count;
}
int main(void)
{
	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 t;
			scanf("%d", &t);
			g[t].push_back(i);
		}
	}
	int s;
	scanf("%d", &s);
	for (int i = 0; i < s; ++i)
	{
		int t;
		scanf("%d", &t);
		printf("%d\n", bfs(t));
	}
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=1010;
vector<int> Adj[maxn];
bool vis[maxn]={false};
int n,limit,num,key,sum;
void BFS(int u){
    queue<int> q,l;                   //两个队列一个存储结点编号，一个存储该点层次
    q.push(u);l.push(0);              //两个队列同出同入（根的层次为0）
    vis[u]=true;
    while(!q.empty()){
        int u=q.front();
        int level=l.front();
        if(level<=limit) sum++;       //累加层次不大于上限的点数量
        q.pop();l.pop();
        for(int i=0;i<Adj[u].size();i++){
            int v=Adj[u][i];
            if(vis[v]==false){
                q.push(v);l.push(level+1); //当前点比父结点层次大1
                vis[v]=true;
            }
        }
    }
}
int main(){
    cin>>n>>limit;
    for(int i=1;i<=n;i++){
        cin>>num;
        for(int j=0;j<num;j++){      //i关注key，则信息可从key传到i，即有key->i的有向边
            cin>>key;
            Adj[key].push_back(i);
        }
    }
    cin>>num;
    for(int i=0;i<num;i++){
        cin>>key;
        sum=0;
        fill(vis+1,vis+n+1,false);
        BFS(key);
        cout<<sum-1<<endl;          //sum为（层次不大于上限的）发送该条信息的人数量，sum-1即为转发者的数量
    }
    return 0;
} 

/*
https://www.nowcoder.com/questionTerminal/920f0f6ad2b94d44b929e2d7f0afdc80
Forwards on Weibo (30) 2018-12-22
General mean: Give you a network and the starting point, require the total munber of node that
the starting point can infect by no more than L step.
Result: 23 minutes to understant the question and 35 minutes to write the code. It is a simple and 
question with a long paragraph, Read the question and understand what that mean is very important.
The first reation is using dfs to solve it, but after it done i realize that dfs seem not fif on 
it question. So I change the method, Get acpected in first shoot but waste some time to debug in
the funtion because I am still not skillfull as yet.
*/
#include"stdafx.h"
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1009;
bool vis[maxn];
vector<int>fan[maxn];
int N, L;
struct node{
    int index;
    int depth;
};
int bfs(int a){
    memset(vis, 0, sizeof(vis));
    int count = 0;
    queue<node>que;
    que.push({ a, 0 });
    while (!que.empty()){
        int temp = que.front().index;
        int depth = que.front().depth;
        que.pop();
        if (depth > L || vis[temp]) continue;
        vis[temp] = 1;
        count++;
        for (int i = 0; i < fan[temp].size(); i++){
            if (!vis[fan[temp][i]]){
                que.push({ fan[temp][i], depth + 1 });
            }
        }
    }
    return count;
}
int main(){
    scanf("%d%d", &N, &L);
    for (int i = 1; i <= N; i++){    //from 1 to N include N
        int mi, t;
        scanf("%d", &mi);
        for ( int j = 0; j < mi; j++){
            scanf("%d", &t);
            fan[t].push_back(i);
        }
    }
    int Q, t;
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++){
        scanf("%d", &t);
        cout << bfs(t)-1 << endl;    //substart the starting point.
    }
    return 0;
}

思路：抄大神写的弗洛伊德算法 求任意两点之间的最短距离 加了注释
教科书般的 Floyd算法。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif


int f[1024][1024];
void better(int &x, int y)
{
    if ((x < 0) || (x > y))
    {
        x = y;
    }
}


int main() {
    int n, m;
    cin >> n >> m;
    memset(f, 0xff, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        int j;
        for (cin >> j; j; --j)
        {
            int x;
            cin >> x;
            f[x][i] = 1;// x 点和 i 点的距离是1
        }
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (f[i][k] >= 0)
            {
                for (int j = 1; j <= n; ++j)
                {
                    if (f[k][j] >= 0)
                    {
                        better(f[i][j], f[i][k] + f[k][j]);// 如果 i j 两点的距离比 i K 
                                                           // 和 k j之间的距离大就改变这i 和 j 之间距离大
                    }
                }
                
            }
        }
    }

    int x;

    for (cin >> x; x; --x)
    {
        int y;
        cin >> y;
        int z = 0;
        for (int i = 1; i <= n; ++i)
        {
            if ((i != y) && (f[y][i] >= 0) && (f[y][i] <= m))// 如果 y 和 i 之间的距离小于 m 层数那么
                                                             // z ++ 个数加加。
            {
                ++z;
            }
        }
        printf("%d\n", z);
    }
    system("pause");
    return 0;
}

package com.zju.algorithem.pat;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ForwardsOnWeibo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();            //the number of users
        int L = in.nextInt();            //the maxinum layer
        int net[][] = new int[N + 1][N + 1];
        for(int i = 1;i <= N;i++){        //创建地图,地图中值为1的代表可以博主可以传给他的粉丝
            int num = in.nextInt();
            for(int j = 0;j < num;j++){
                int k = in.nextInt();
                net[k][i] = 1;
            }
        }
        int searchNum = in.nextInt();
        int search[] = new int[searchNum];        //要查询的结点的编号
        int result[] = new int[N + 1];        //最终的结果
        Queue<Integer> index = new LinkedList<Integer>();        //存放结点下标
        Queue<Integer> depth = new LinkedList<Integer>();        //存放对应的深度
        for(int i = 0;i < searchNum;i++){
            search[i] = in.nextInt();
        }
        //利用bfs广度优先搜索来找有向图相应点i所能到达距离小于L的数量
        for(int i = 0;i < searchNum;i++){
            int num = search[i];
            boolean visited[] = new boolean[N + 1];
            index.add(num);
            depth.add(0);
            result[num] = -1;
            visited[num] = true;
            while(!index.isEmpty()){
                int node = index.poll();
                int dp = depth.poll();
                result[num]++;            //最后结果计数
                if(dp < L){                //如果出队列的结点的深度小于L
                    for(int j = 1;j <= N;j++){
                        if(net[node][j] == 1 && !visited[j]){
                            index.add(j);
                            depth.add(dp + 1);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        for(int i = 0;i < searchNum;i++){
            System.out.println(result[search[i]]);
        }
    }

}

	

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

vector<list<int> > g;

int query(int src, int n, int L)
{
	vector<int> color(n + 1, 0);
	queue<pair<int, int> > q;
	q.push(make_pair(src, 0));
	color[src] = 1;

	int res = 0;
	while (!q.empty()){
		pair<int, int> p = q.front();
		q.pop();

		if (p.second <= L){
//			cout << p.first << endl;
			res++;
		}
		else continue;

		list<int>::iterator it = g[p.first].begin();
		for (; it != g[p.first].end(); it ++){
			if (color[*it] == 0){
				q.push(make_pair(*it, p.second + 1));
				color[*it] = 1;
			}
		}

		color[p.first] = 2;
	}

	return res - 1;
}

int main()
{
	int K, M, N, L;
	cin >> N >> L;
	
	for (int i = 0; i <= N; i++){
		list<int> tmp;
		g.push_back(tmp);
	}
	
	for (int i = 1; i <= N; i++){
		cin >> M;
		while (M--){
			int x;
			cin >> x;
			g[x].push_back(i);
		}
	}

	cin >> K;
	while (K--){
		int x;
		cin >> x;
		cout << query(x, N, L) << endl;
	}
	return 0;
}

#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
#define MAXSIZE 1000
using namespace std;
typedef struct{
	int V_num;
	int E_num;
	int matrix[MAXSIZE][MAXSIZE];
}web,*Web; 

void Crt(Web W,int N){
	W->V_num = N;
	W->E_num = 0;
	int num;
	int index;
	for(int i=1; i<=N; i++)
		for(int j=1; j<=N; j++)
			W->matrix[i][j] = 0;
	for(int i=1; i<=N; i++){
		cin>>num;
		W->E_num = W->E_num + 1;
		for(int j=0; j<num; j++){
			cin>>index;
			W->matrix[index][i]= 1;
		}
	}
}

int Cal(Web W,int aim,int L){
	int num = 0;
	int Layer = 1;
	int pre_num = 1;
	int b_num = 1;
	queue<int> Q;
	vector<bool> visited(W->V_num,false);
	int p = aim;
	Q.push(p);
	visited[p] = true;
	while( !Q.empty() && Layer <=L ){
		b_num = pre_num;    
		pre_num = 0;                                   //本层顶点等于上一层邻接顶点总和 
		for(int k=0; k<b_num; k++){                    //先把本层顶点都遍历统计完 
			p = Q.front();
			Q.pop();
			for(int i=1; i<=W->V_num; i++){
				if(W->matrix[p][i] && !visited[i]){
					num++;
					visited[i] = true;
					Q.push(i);
					pre_num++;
				}
			}
		}
		Layer++;
	}
	return num;
}

void Process(Web W,int L){
	int N,temp;
	cin>>N;
	for(int i=0; i<N; i++){
		cin>>temp;
		cout<<Cal(W,temp,L)<<endl;
	}
}

int main(){
	Web W;
	W = (web *)malloc(sizeof(web));
	int N,L;
	cin>>N>>L;
	Crt(W,N);
	Process(W,L);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int Max=1010;
bool visit[Max]= {0};

struct node {
	int id;
	int layer;
	node() {}
	node(int x):id(x),layer(0) {}
};

vector<node> G[Max];

int BST(int s,int l) {
	int answer=0;
	queue<node> q;
	q.emplace(node(s));
	visit[q.front().id]=1;
	while(!q.empty()) {
		node u=q.front();
		q.pop();
		for(int i=0; i<G[u.id].size(); i++) {
			node next(G[u.id][i]);
			next.layer=u.layer+1;
			if(!visit[next.id]&&next.layer<=l) {
				q.emplace(next);
				visit[next.id]=1;
				answer++;
			}
		}
	}
	return answer;
}

int main() {
	node user;
	int n,l,num,id;
	cin>>n>>l;
	for(int i=1; i<=n; i++) {
		user.id=i;
		cin>>num;
		for(int j=0; j<num; j++) {
			cin>>id;
			G[id].emplace_back(user);
		}
	}
	int k,s;
	cin>>k;
	for(int i=0; i<k; i++) {
		memset(visit,0,sizeof(visit));
		cin>>s;
		int answer=BST(s,l);
		cout<<answer<<endl;
	}
	return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> ve[1009];
bool as[1009];
void rant(int x,int l);
void print(int n);
int main()
{
	int n, l;
	cin >> n >> l;
	for (int i = 0; i <= n; i++) {
		ve[i].push_back(1);
	}
	for (int i = 1; i <= n; i++) {
		int m;
		cin >> m;
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			ve[x].push_back(i);
		}
	}
	int k;
	cin >> k;
	for (int i = 0; i < k; i++) {
		int j;
		cin >> j;
		fill(as, as + 1009, 0);
		rant(j,l);
		print(n);
	}

	return 0;
}
void rant(int x,int l)
{
	as[x] = true;
	if (l == 0) return;
	for (int i = 1; i <ve[x].size(); i++) {
		as[ve[x][i]] = true;
		rant(ve[x][i], l - 1);
	}
	return;
}
void print(int n)
{
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		if (as[i] == true) {
			ans++;
		}
	}
	cout << ans-1 << endl;
}

更多PAT甲级题解尽在我的个人博客--acking-you.github.io

题目

OJ平台

题目大意

这题看了描述后，大概就能清楚题目是这么个意思：

• 输入： 输入N个人，并给出这N个人的关注列表。以及层级限制 L 和 K 次询问。
• 输出： K次询问，每次询问第 i 个人发博客后，在它树形关注图 L 层级内最多有多少人收到这个博客通知？

把题目往这一摆，很快发现，这个题目就是一个普通的BFS，只不过建图的时候需要注意：输入给出的是每个人的关注列表，我们需要根据关注列表得出每个人被哪些人关注了。

代码拆解

输入处理

int N, L; //给出的用户数\可以间接转发的树的高度
vector<int> node[1001]; //形成树形结构--存储每个用户被关注哪些用户所关注
vector<int> question;   //存储问题

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> L;
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        while (t--) { //这个由于是输入的每个人的关注列表，需要转换为某个人被关注列表
            int val;
            cin >> val;
            node[val].push_back(i); //更新每个树的子节点
        }
    }
    int c;
    cin >> c;
    while (c--) { //输入询问的问题，其实也可以在这里打印，只不过会让单个程序变得复杂
        int val;
        cin >> val;
        question.push_back(val);
    }
}

输出处理

//@bfs获取每次询问的答案
int get_res(int n) {
    bitset<1001> check(0);  //用于防止重复计数
    check[n] = 1;          //不能自己给自己转发
    queue<int> Q;         //用于BFS层序遍历
    Q.push(n);
    int res = 0, step = 0;
    while (!Q.empty() && step < L) {
        for (int i = Q.size(); i > 0; i--) {
            int t = Q.front();
            Q.pop();
            for (auto &&tt:node[t]) {
                if (!check[tt]) {
                    res++;
                    Q.push(tt);
                    check[tt] = 1;
                }
            }
        }
        step++;
    }
    return res;
}
//@打印答案
void print() {
    int sz = question.size();
    for (int i = 0; i < sz; i++) {
        if (i != sz - 1) {
            cout << get_res(question[i]) << '\n';
        } else {
            cout << get_res(question[i]);
        }
    }
}

整合代码得出答案

效率应该在这题来说是数一数二了(还能通过直接在输入阶段打印结果提升效率的。

#include<bits/stdc++.h>
using namespace std;
int N, L; //给出的用户数\可以间接转发的树的高度
vector<int> node[1001]; //形成树形结构--存储每个用户被关注哪些用户所关注
vector<int> question;   //存储问题

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> L;
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        while (t--) { //这个由于是输入的每个人的关注列表，需要转换为某个人被关注列表
            int val;
            cin >> val;
            node[val].push_back(i); //更新每个树的子节点
        }
    }
    int c;
    cin >> c;
    while (c--) { //输入询问的问题，其实也可以在这里打印，只不过会让单个程序变得复杂
        int val;
        cin >> val;
        question.push_back(val);
    }
}

//@bfs获取每次询问的答案
int get_res(int n) {
    bitset<1001> check(0);  //用于防止重复计数
    check[n] = 1;              //不能自己给自己转发
    queue<int> Q;            //用于BFS层序遍历
    Q.push(n);
    int res = 0, step = 0;
    while (!Q.empty() && step < L) {
        for (int i = Q.size(); i > 0; i--) {
            int t = Q.front();
            Q.pop();
            for (auto &&tt:node[t]) {
                if (!check[tt]) {
                    res++;
                    Q.push(tt);
                    check[tt] = 1;
                }
            }
        }
        step++;
    }
    return res;
}
//@打印答案
void print() {
    int sz = question.size();
    for (int i = 0; i < sz; i++) {
        if (i != sz - 1) {
            cout << get_res(question[i]) << '\n';
        } else {
            cout << get_res(question[i]);
        }
    }
}

int main() {
    Input();
    print();
    return 0;
}

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

int N,L,K;

vector<int> v[1010]; //邻接表
bool inq[1010]={false};
int follow[1010]={0};
int layer[1010]={0};


void BFS(int n){
    queue<int>q;
    q.push(n);
    inq[n]=true;
    layer[n]=0;
    while(!q.empty()){
        int t=q.front();
        inq[t]=true;
        q.pop();
        for(int i=0;i<v[t].size();i++){
            if(!inq[v[t][i]]){ //未被加入队中
                layer[v[t][i]]=layer[t]+1;
                if(layer[v[t][i]]<=L){
                    follow[n]++;
                    inq[v[t][i]]=true;
                    q.push(v[t][i]);
                }
            }
        }
    }
}

void BFSTravel(){
    for(int i=1;i<=N;i++){
        BFS(i);
        memset(inq,false,sizeof(inq));
    }
}

int main(){
    cin>>N>>L;
    int num;
    for(int i =1;i<=N;i++){
        cin>>num;
        for(int j=0;j<num;j++){
            int id;
            cin>>id;
            v[id].push_back(i);
        }
    }
    
    BFSTravel();
    cin>>K;
    for(int i=0;i<K;i++){
        int id;
        cin>>id;
        cout<<follow[id]<<endl;
    }

}