首页 > 试题广场 >

挑选镇长

[编程题]挑选镇长
  • 热度指数：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
算法知识视频讲解
添加回答
推荐
toraoh头像 toraoh
请无视以下题面补完+出数据+写标程的人的胡言乱语：

注意到整张图是有向图，要求你找到所有其他点都有边直接指向A，但A不指向其他任何人，满足这样的条件的A的个数，以及具体是谁。
首先说两个离散数学里有向图的概念：入度和出度。
入度，指的是有向图中终点为某个特定点A的边的数量。相对的，出度就是指，有向图中起点为某个特定点A的边的数量。

现在根据题目意思思考一下：
要在大小为n的图中，找到点，使得其他n-1个点都有边直接指向，但是它不指向任何点。
鉴于题目里给出的限定条件（不含重边，但有自环），也就是说，我们在去掉自环的图上找点，这个点有n-1个入度，出度为0就行。
因为没有重边啊，所以这n-1个入度边对应的起点为其他n-1个点，加上被指向这个点自己，刚好就整张图上点的数量 N

冷静一下，也就是说，这个题根部不需要vector、list什么的存结果，最多只有1个答案！
于是，标程的写法是，直接读进来的边，丢弃自环，算入度与出度，最后遍历一遍，找到唯一一个入度为n-1，出度为0的点，就是正解了！（找不到要输出0，记得多一个换行，样例里有说明了）

（顺便请思考一下，如果说明了有重边，如何把重边高效的去除呢？）

顺带一提，1个人0个认识关系的时候是有解的，那一个人就是镇长了，2个人相互都不认识的时候，谁都当不了镇长，这个是加入了测试数据的，不管削弱前还是削弱后。

===========================================
当然有幸看到一些错误写法。
比如开了1000*1000的数组，估计想邻接矩阵存图，但是完全没必要啊……
还有，说了n个人编号1到n，不相信，然后开了个结构体数组，成员分别是编号，以及入度和出度——大哥，你用map也比你O(n)找过去强，你这一搞，时间复杂度直接O(n*m)，10万*30万，不卡你卡谁！

最后跑了一圈下来，1秒的时限下只有1个人通过（我本意也不是1秒时限，是Java5秒，其他语言2秒），没办法了，时限改对以后还把数据削弱的只有80%那些小数据了。


以下是标程。 

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXN=100000;
int indeg[MAXN+5],outdeg[MAXN+5];

int main(){
	int T,n,m;
	int a,b;
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			indeg[i]=outdeg[i]=0;
		}
		for(int i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			if(a!=b){
				outdeg[a]++;
				indeg[b]++;
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			if(indeg[i]==n-1 && outdeg[i]==0){
				ans=i;
				break;
			}
		}
		if(ans==0){
			puts("0");
			puts("");
		}else{
			puts("1");
			printf("%d\n",ans);
		}
	}
    return 0;
}
 

还有前5组手造小数据：
1 0

2 0

3 2
1 2
3 2

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

2 3
1 1
2 1
1 2

编辑于 2015-08-13 21:20:30 回复(9)
Python
离疏头像 离疏 
T=int(input())
for i in range(T):
    n,m=list(map(int,input().split()))
    matrix=[[0,0]for i in range(n)]#matrix[0],matrix[1]分别为出度和入度
    for i in range(m):
        x=list(map(int,input().split()))
        A,B=x[0],x[1]
        if A!=B:#去掉自环
            matrix[A-1][0]+=1#算入度与出度
            matrix[B-1][1]+=1
    num,people=0,[]
    for i in range(n):
        if matrix[i]==[0,n-1]:#找到入度为n-1，出度为0的点
            num+=1
            people.append(i+1)
    print(num)
    print(' '.join(str(x) for x in people) if people!=[] else '')

发表于 2018-08-22 16:01:16 回复(0)
Python
华科平凡头像 华科平凡

python solution

题目的样例可以忽略不看，完全是错误的答案。

for _ in range(int(input())):
    a, b = map(int, input().split())
    know, known = [0] * a, [0] * a
    for __ in range(b):
        guanxi = list(map(int, input().split()))
        if guanxi[0] != guanxi[1]:
            know[guanxi[0] - 1] += 1
            known[guanxi[1] - 1] += 1
    have = False
    for i in range(a):
        if know[i] == 0 and known[i] == a - 1:
            have = True
            print(1)
            print(i + 1)
    if not have:
        print(0)
        print("")
发表于 2017-11-07 19:22:20 回复(0)
Python
suanfalianxi头像 suanfalianxi
def choose_team(s,t,n):
    '''
    n = raw_input()
    n = int(n)
    s = []
    t = []
    t1 = 0
    t2 = 0
    h = 0
    s1 = {}
    for i in range(n):
        s.append(raw_input().split(' '))
        for i in range(int(s[i][1])):
            if int (s[i][1])!=0:
                t.append(raw_input().split(' '))
    '''  
    t1 = 0
    t2 = 0
    h = 0
    s1 = {}         
    for i in range(n):
        if int(s[i][1])==0:
            print 0
            print ' '
        else:
            for j in range(i):
                t1 += int(s[j][1])
            t2 = t1+ int(s[i][1])
            for k in range(t1,t2):
                if int(t[k][1])!=int(t[k][0]):
                    if int(t[k][1]) not in s1:
                        s1[int(t[k][1])] =1
                    else:
                        s1[int(t[k][1])] += 1
            a =  sorted(s1.items(),key=lambda item:item[1],reverse=True)[0][1]
            if a==int (s[i][0])-1:
                for key,value in s1.items():
                    if value == a:
                        h +=1
                print h
                if h>1:
                    for key,value in s1.items():
                        if value == a:
                            print key,
                else:
                    for key,value in s1.items():
                        if value == a:
                            print key
            else:
                print 0
                print ' '
            t1 = 0
            t2 = 0
            h = 0
            s1 = {}
有一个疑问输入 2 0明明输出结果是 0和下一行的空格为什么我测试时说应该输出1呢 代码并没有通过 可是在本机可以运行啊
发表于 2017-07-22 19:12:17 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

挑选镇长

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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