首页 > 试题广场 >

挑选镇长

[编程题]挑选镇长
  • 热度指数：7436 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
360员工桂最近申请了一个长假，一个人背着包出去自助游了。
路上，他经过了一个小镇，发现小镇的人们都围在一棵树下争吵。桂上前询问情况，得知小镇的人们正缺一个镇长，他们希望能选一个知名又公正的镇长，即，大家希望能选出一个人，所有人都认识他，但同时他不认识镇上除自己以外的其他人（在此，我们默认每个人自己认识自己）。可是小镇里的人太多了，一下子大家谁也说服不了谁。
“这简单啊。”桂表示。于是他一下子统计出来了镇上人们相互之间的认识关系，并且一下子找到了合适的镇长人选。
现在你手上也拿到了这样一份认识关系的清单。其中上面给出的认识关系是单向的，即，A认识B与B认识A是相互独立的，只给出A认识B就不能认为B认识A，例如，我认识你，你不一定认识我。而且，这里的认识关系也不具有传递性，即，A认识B，B认识C，但这不代表A认识C。同时，为了方便处理，这份清单中，镇上的N个人依次编号为1到N。你能否像桂一样快速找到合适的镇长人选呢？

输入描述:
首先一个正整数T（T≤20），表示数据组数。
之后每组数据的第一行有2个整数n  和m  (1≤n≤105 ,0≤m≤3×105 )，依次表示镇上的人数和相互之间的认识关系数。
之后m行，第 i 行每行两个数Ai和Bi   (1≤Ai ,Bi ≤n  )，表示Ai认识Bi。（保证没有重复的认识关系，但可能存在自己认识自己的认识关系）
保证所有数据中80%的数据满足n≤1000,m≤10000


输出描述:
一共2T 行，每组数据对应2行。
第一行，一个整数，表示你所找出来的合适的镇长人选人数num i   。
第二行，num i 个整数，每两个数中间用空格隔开，表示你所选的合适的镇长的编号。
特别的，如果并没有找到合适的镇长，第一行输出一个数0，第二行留空即可（参见样例）。
示例1

输入

3
2 0
3 2
1 2
3 2
4 5
1 1
2 1
3 1
4 1
3 3

输出

0

1
2
1
1
算法知识视频讲解
开通博客
头像 重生之我要当分子
发表于 2025-01-01 02:09:43
解题思路 我们需要找到一个镇长候选人，满足以下条件： 所有人都认识这个候选人。 这个候选人不认识其他任何人（除了自己）。 为了解决这个问题，我们可以使用图的概念： 将每个人视为图中的一个节点。 将“认识”关系视为有向边。 算法步骤： 构建图：使用两个数组cd和rd来记录每个人的出度和入度。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客576763251号
发表于 2024-09-18 19:29:41
#include <stdio.h> #include <math.h> void init(int arr[],int len){ int k=0; for(k=0;k<len;k++){ arr[k]=0; } } int 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 图 测试工程师 PHP工程师 c#工程师 2016 测试开发工程师 大数据开发工程师 360集团 Java工程师
来自：360公司2016研发...
难度：
66条回答 18224浏览

热门推荐

通过挑战的用户

查看代码

相关试题

挑选镇长

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号