网易游戏面试题 - 谁收到了消息

前端之家收集整理的这篇文章主要介绍了网易游戏面试题 - 谁收到了消息前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题意

这里写图片描述

思路

乍1看题,冒出来的思路是,将每一个用户凡是在同1个群的两个用户看作是1条无向边,这样所有群的所有用户之间的联系就转化为了1张图,然后以官方用户(id=1)为出发点,计算所有可以到达的节点的总数,dfs便可,按着这个思路正准备开始写,发现id max为100000,2维数组是开不了了,临界表的话未免也太繁琐了。
才突然意想到我们只需要对所有用户之间的连通性进行判断,至于具体的连通顺序根本不需要肯定,那末呼之欲出了,并查集
在并查集基础之上,用每一个集的顶节点为标识,记录每一个集的节点总数,在集合并时对总数进行更新,1个数组就能够解决

代码

#include <iostream> #include <cstdio> using namespace std; #define N 100009 int p[N]; int fa[N]; int d[1009]; int find(int x) { if(fa[x] == -1) return x; return fa[x] = find(fa[x]); } int main() { int m; scanf("%d",&m); memset(fa,-1,sizeof(fa)); for(int i=0; i<=100000; i++) p[i] = 1; for(int i=0; i<m; i++) { int k; scanf("%d",&k); for(int j=0; j<k; j++) scanf("%d",&d[j]); int x = find(d[0]); for(int j=1; j<k; j++) { int y = find(d[j]); if(x != y) { fa[y] = x; p[x] += p[y]; } } } int x = find(1); printf("%d\n",p[x]-1); return 0; }

猜你在找的PHP面试题相关文章