网站备案起名要求,网站的格式分类,微信做兼职什么网站好,灰色网站怎么做seo文章目录 题目题目翻译深度优先搜索#xff08;dfs#xff09;宽度优先搜索#xff08;bfs#xff09;总结 原题链接
题目 题目翻译
微博被称为中国的推特。在微博上#xff0c;一个用户可能有很多粉丝#xff0c;也可能关注许多其他用户。因此#xff0c;通过粉丝关系… 文章目录 题目题目翻译深度优先搜索dfs宽度优先搜索bfs总结 原题链接
题目 题目翻译
微博被称为中国的推特。在微博上一个用户可能有很多粉丝也可能关注许多其他用户。因此通过粉丝关系形成了一个社交网络。当一个用户在微博上发表帖子时他/她所有的粉丝都可以查看和转发他/她的帖子然后这些帖子可以被他们的粉丝再次转发。现在假设只计算L级的间接粉丝需要计算任何一个特定用户的最大潜在转发量。
输入格式 每个输入文件包含一个测试用例。对于每个案例第一行包含两个正整数N≤1000用户的数量L≤6被计算的间接粉丝的级别数。因此所有用户都被假设编号从1到N。然后是N行每行的格式如下 M[i] user_list[i] 其中 M[i]≤100是用户[i]关注的总人数user_list[i] 是用户[i]关注的 M[i] 个用户的列表。保证没有人会关注自己。所有数字之间用空格分隔。
然后最后给出一个正整数 K后面跟着 K 个用户ID用于查询。
输出格式
对于每个用户ID你需要在一行中打印出这个用户可以触发的最大潜在转发量假设每个可以看到初始帖子的人都会转发一次并且只计算L级的间接粉丝。
基本思路
求一个用户的最大潜在转发量就是一层一层地去找粉丝数不超过L层。每次一层一层去找粉丝数时我们需要知道当前用户是在第几层是否转发过到这里我一开始想到的是用dfs(深度优先搜索)但是最后一个用例超时了应该是递归调用太多了爆栈了。所以得用bfs(宽度优先搜索)将该层的用户编号和该用户的层数用一个队列存储起来然后遍历每个用户的粉丝编号如果没有转发过答案就1如果当前层数最大层数L就将它的粉丝编号和它的层数入队
深度优先搜索dfs
思路比较简单先定义一个用户结构体userID结构体里面存储vector容器vector存储关注该用户的粉丝编号。再定义结构体数组user[M]将全部用户编号以及该用户的粉丝编号存储起来。
struct userID {vectorint m;
}user[M];再来看递归函数dfs的写法将当前用户的粉丝编号遍历一遍vis数组用来标记当前用户是否转发过如果为false最大转发量就1然后标记当前用户为true。然后再判断该层是否小于最大层数L如果小于就继续递归该粉丝和下一层层数。
void dfs(int id,int l)
{for (int i 0; i user[id].m.size(); i){if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;}if(lL){dfs(user[id].m[i],l1);}}
}完整代码
#includeiostream
#includevector
#includecstring
using namespace std;
const int M 1010;
typedef long long ll;
int N, L, K;
int k[M];
bool vis[M];
struct userID {vectorint m;
}user[M];
ll ans 0;
void dfs(int id,int l)
{for (int i 0; i user[id].m.size(); i){if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;}if(lL){dfs(user[id].m[i],l1);}}
}
int main()
{cin N L;for(int i1;iN;i){int u;cin u;for (int j 0; j u; j){int x;cin x;user[x].m.push_back(i);}}cin K;for (int i 0; i K; i){cin k[i];}for (int i 0; i K; i){ans 0;memset(vis, false, sizeof vis);vis[k[i]] true;dfs(k[i], 1);cout ans endl;}return 0;
}通过评测结果发现只过了90%的样例最后一个运行超时。可能原因就是递归调用太多导致栈溢出。 递归搜索dfs不行可以尝试使用非递归搜索bfs
宽度优先搜索bfs
延续上述思路先创建一个队列该队列存储的是对组pairint,int对组第一个数是用户编号id第二个数是当前用户所在的层数
queuepairint, int q;
q.push({用户编号id,用户所在的层数});步骤 1判断当前队列是否为空如果不为空获取队头 2遍历该用户的所有关注者——如果没有转发过则最大转发量1再将该关注者标志为转发过判断该用户的当前层数是否小于最大层数L如果小于则将该关注者的编号和所在层数入队注意关注者的所在层数要加一
q.push({ user[id].m[i],level 1 });将发表帖子的用户编号以及层数层数为1入队再重复步骤(1)(2) 直到队列为空
void bfs(int id)
{queuepairint, int q;q.push({id,1});while (!q.empty()){auto node q.front();q.pop();int id node.first;int level node.second;for (int i 0; i user[id].m.size(); i){if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;}if (level L){q.push({ user[id].m[i],level 1 });}}}
}完整代码
#includeiostream
#includecstring
#includequeue
using namespace std;
const int M 1010;
typedef long long ll;
int N, L, K;
int k[M];
bool vis[M];
struct userID {vectorint m;
}user[M];
ll ans 0;
void bfs(int id)
{queuepairint, int q;q.push({id,1});while (!q.empty()){auto node q.front();q.pop();int id node.first;int level node.second;for (int i 0; i user[id].m.size(); i){if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;}if (level L){q.push({ user[id].m[i],level 1 });}}}
}
int main()
{cin N L;for(int i1;iN;i){int u;cin u;for (int j 0; j u; j){int x;cin x;user[x].m.push_back(i);}}cin K;for (int i 0; i K; i){cin k[i];}for (int i 0; i K; i){ans 0;memset(vis, false, sizeof vis);vis[k[i]] true;bfs(k[i]);cout ans endl;}return 0;
}通过评测结果发现还是只过了90%的样例报错结果是内存超限那么可能的原因就是堆内存溢出。 我们仔细看下面的代码可以发现不管当前用户的关注者是否转发过帖子只要当前用户的层数小于最大层数L那么该用户的所有关注者都会入队。实际上是没有必要的如果该用户的某个关注者已经转发过再将其入队会造成重复查询到下一层再查询该关注者的所有关注者时发现已经全部转发过使内存消耗更大从而导致堆内存溢出。
for (int i 0; i user[id].m.size(); i)
{if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;}if (level L){q.push({ user[id].m[i],level 1 });}
}那么应该怎么改——只有当前用户的关注者没有转发过且当前层数小于最大层数L才能将关注者编号和下一层层数入队。
for (int i 0; i user[id].m.size(); i)
{if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;if (level L){q.push({ user[id].m[i],level 1 });}}
}这种写法相当于剪枝就是将没有必要搜索而且不影响结果的分支去除掉这样既提高了搜索效率也节省了计算资源。 剪枝是一种在算法中减少搜索空间的技术特别是在解决优化问题和决策问题时使用。它的核心思想是在搜索过程中提前排除那些不可能产生最优解或者不符合特定条件的分支从而减少不必要的计算和资源消耗。 还有一种剪枝的写法个人不建议
for (int i 0; i user[id].m.size(); i)
{//不推荐这种写法因为可能还要将最高层的用户编号入队列但是已经判断过最高层的用户是否转发过了
// if (vis[user[id].m[i]] false levelL)
// {
// ans 1;
// vis[user[id].m[i]] true;
// q.push({ user[id].m[i],level 1 });
// }//推荐这种写法if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;if (level L){q.push({ user[id].m[i],level 1 });}}
}完整代码
#includeiostream
#includecstring
#includequeue
using namespace std;
const int M 1010;
typedef long long ll;
int N, L, K;
int k[M];
bool vis[M];
struct userID {vectorint m;
}user[M];
ll ans 0;
void bfs(int id)
{queuepairint, int q;q.push({id,1});while (!q.empty()){auto node q.front();q.pop();int id node.first;int level node.second;for (int i 0; i user[id].m.size(); i){if (vis[user[id].m[i]] false){ans 1;vis[user[id].m[i]] true;if (level L){q.push({ user[id].m[i],level 1 });}}}}
}
int main()
{cin N L;for(int i1;iN;i){int u;cin u;for (int j 0; j u; j){int x;cin x;user[x].m.push_back(i);}}cin K;for (int i 0; i K; i){cin k[i];}for (int i 0; i K; i){ans 0;memset(vis, false, sizeof vis);vis[k[i]] true;bfs(k[i]);cout ans endl;}return 0;
}通过评测结果发现通过了全部样例
个人的另一种写法
此写法直接开辟了二维动态数组省去了创建结构体和结构体数组但实际上大同小异。
#includeiostream
#includecstring
#includequeue
using namespace std;
const int M 1010;
typedef long long ll;
int N, L, K;
int k[M];
bool vis[M];
vectorvectorint vc(M);
ll ans 0;
void bfs(int id)
{queuepairint, int q;q.push({id, 1});while (!q.empty()){auto node q.front();q.pop();int id node.first;int level node.second;for (int i 0; i vc[id].size(); i){if (vis[vc[id][i]] false){ans 1;vis[vc[id][i]] true;if (level L){q.push({vc[id][i], level 1});}}}}
}
int main()
{cin N L;for(int i1;iN;i){int u;cin u;for (int j 0; j u; j){int x;cin x;vc[x].push_back(i);}}cin K;for (int i 0; i K; i){cin k[i];}for (int i 0; i K; i){ans 0;memset(vis, false, sizeof vis);vis[k[i]] true;bfs(k[i]);cout ans endl;}return 0;
}评测结果显示通过了全部样例
yxc的写法
此写法用邻接表来存储图需要注意的是一共有1000个点每个点最多存100条边所以点数N可以开1e310边数M最多为1e510。
#includeiostream
#includecstring
#includequeue
using namespace std;//点数和边数
const int N1e310,M1e510;int n,l;
int h[N],e[M],ne[M],idx; //用邻接表来存储图
bool st[N]; //状态数组//头节点
void add(int a,int b){e[idx]b,ne[idx]h[a],h[a]idx;
}int bfs(int start){queueint q;memset(st, 0, sizeof st);q.push(start); //队列初始化st[start]true;int res0;//l为关注着的层数for(int i0;il;i){ //i为每层的关注者int szq.size();//注意这个while中sz为每层关注着的人数所以要暂存while(sz--){auto tq.front();q.pop();//遍历start的第i层关注者for(int jh[t];j!-1;jne[j]){auto xe[j]; //e[j]存放关注者的编号if(!st[x]){q.push(x);st[x]true;res;}}}}return res;
}int main(){cinnl;memset(h,-1,sizeof h);for(int i1;in;i){int cnt; //第i名用户关注的总人数cincnt;while(cnt--){int x;cinx;add(x,i); //i是x的粉丝让x指向i}}int m;cinm;while(m--){int x;cinx;coutbfs(x)endl;}return 0;
}评测结果显示通过了全部样例
总结
这道题的英文单词有点难理解比如forward转发follower粉丝indirect间接地
这些单词需要结合上下文才能慢慢读懂比如forward很多人会翻译成向前的意思
对于深度优先搜索dfs和宽度优先搜索bfs我们优先考虑能不能使用bfs剪枝一次通过因为dfs的局限性有点大数据稍微大一点就很容易超时当然也可以通过dfs剪枝来降低时间复杂度但是不确定能不能通过
到这里就结束啦对以上内容有异议的欢迎大家来讨论。 文章转载自： http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.pccqr.cn.gov.cn.pccqr.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.xkwrb.cn.gov.cn.xkwrb.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.jnrry.cn.gov.cn.jnrry.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.rkfxc.cn.gov.cn.rkfxc.cn http://www.morning.sqmlw.cn.gov.cn.sqmlw.cn http://www.morning.rqrh.cn.gov.cn.rqrh.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.fqmcc.cn.gov.cn.fqmcc.cn http://www.morning.cjcry.cn.gov.cn.cjcry.cn http://www.morning.lbbrw.cn.gov.cn.lbbrw.cn http://www.morning.cbpkr.cn.gov.cn.cbpkr.cn http://www.morning.wjtxt.cn.gov.cn.wjtxt.cn http://www.morning.rfxw.cn.gov.cn.rfxw.cn http://www.morning.qytpt.cn.gov.cn.qytpt.cn http://www.morning.sqnxk.cn.gov.cn.sqnxk.cn http://www.morning.crfyr.cn.gov.cn.crfyr.cn http://www.morning.brscd.cn.gov.cn.brscd.cn http://www.morning.jbqwb.cn.gov.cn.jbqwb.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.qtryb.cn.gov.cn.qtryb.cn http://www.morning.fjshyc.com.gov.cn.fjshyc.com http://www.morning.rnjgh.cn.gov.cn.rnjgh.cn http://www.morning.hxpff.cn.gov.cn.hxpff.cn http://www.morning.fnlnp.cn.gov.cn.fnlnp.cn http://www.morning.pfkrw.cn.gov.cn.pfkrw.cn http://www.morning.gjlxn.cn.gov.cn.gjlxn.cn http://www.morning.wzwyz.cn.gov.cn.wzwyz.cn http://www.morning.mhcft.cn.gov.cn.mhcft.cn http://www.morning.jkcnq.cn.gov.cn.jkcnq.cn http://www.morning.byjwl.cn.gov.cn.byjwl.cn http://www.morning.rqfkh.cn.gov.cn.rqfkh.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.tzzfy.cn.gov.cn.tzzfy.cn http://www.morning.hhboyus.cn.gov.cn.hhboyus.cn http://www.morning.hptbp.cn.gov.cn.hptbp.cn http://www.morning.gnfkl.cn.gov.cn.gnfkl.cn http://www.morning.gsyns.cn.gov.cn.gsyns.cn http://www.morning.nbwyk.cn.gov.cn.nbwyk.cn http://www.morning.wnbpm.cn.gov.cn.wnbpm.cn http://www.morning.wpmqq.cn.gov.cn.wpmqq.cn http://www.morning.mingjiangds.com.gov.cn.mingjiangds.com http://www.morning.aishuxue.com.cn.gov.cn.aishuxue.com.cn http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.gediba.com.gov.cn.gediba.com http://www.morning.jwmws.cn.gov.cn.jwmws.cn http://www.morning.synkr.cn.gov.cn.synkr.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.nrcbx.cn.gov.cn.nrcbx.cn http://www.morning.cbnlg.cn.gov.cn.cbnlg.cn http://www.morning.zmwzg.cn.gov.cn.zmwzg.cn http://www.morning.gprzp.cn.gov.cn.gprzp.cn http://www.morning.nnpfz.cn.gov.cn.nnpfz.cn http://www.morning.wylpy.cn.gov.cn.wylpy.cn http://www.morning.ybyln.cn.gov.cn.ybyln.cn http://www.morning.kcwkt.cn.gov.cn.kcwkt.cn http://www.morning.kgqww.cn.gov.cn.kgqww.cn http://www.morning.rycbz.cn.gov.cn.rycbz.cn http://www.morning.prjns.cn.gov.cn.prjns.cn http://www.morning.wnbqy.cn.gov.cn.wnbqy.cn http://www.morning.pjqxk.cn.gov.cn.pjqxk.cn http://www.morning.gjlxn.cn.gov.cn.gjlxn.cn http://www.morning.c7498.cn.gov.cn.c7498.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.prysb.cn.gov.cn.prysb.cn http://www.morning.wjlbb.cn.gov.cn.wjlbb.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.tpyrn.cn.gov.cn.tpyrn.cn http://www.morning.nkiqixr.cn.gov.cn.nkiqixr.cn http://www.morning.zlces.com.gov.cn.zlces.com http://www.morning.ndxmn.cn.gov.cn.ndxmn.cn http://www.morning.sdhmn.cn.gov.cn.sdhmn.cn http://www.morning.bwkhp.cn.gov.cn.bwkhp.cn http://www.morning.hzryl.cn.gov.cn.hzryl.cn http://www.morning.ljbm.cn.gov.cn.ljbm.cn
