360员工桂最近申请了一个长假，一个人背着包出去自助游了。
路上，他经过了一个小镇，发现小镇的人们都围在一棵树下争吵。桂上前询问情况，得知小镇的人们正缺一个镇长，他们希望能选一个知名又公正的镇长，即，大家希望能选出一个人，所有人都认识他，但同时他不认识镇上除自己以外的其他人（在此，我们默认每个人自己认识自己）。可是小镇里的人太多了，一下子大家谁也说服不了谁。
“这简单啊。”桂表示。于是他一下子统计出来了镇上人们相互之间的认识关系，并且一下子找到了合适的镇长人选。
现在你手上也拿到了这样一份认识关系的清单。其中上面给出的认识关系是单向的，即，A认识B与B认识A是相互独立的，只给出A认识B就不能认为B认识A，例如，我认识你，你不一定认识我。而且，这里的认识关系也不具有传递性，即，A认识B，B认识C，但这不代表A认识C。同时，为了方便处理，这份清单中，镇上的N个人依次编号为1到N。你能否像桂一样快速找到合适的镇长人选呢？
[编程题]挑选镇长
- 热度指数：7436 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
首先一个正整数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
镇长需要满足的要求就是：
1、所有人都认识镇长（入度=n-1）
2、镇长不认识任何人（出度=0）
使用2个长度为n的数组，来分别统计每个人的出度和入度。
另外，注意碰到自己认识自己的输入，直接跳过即可。
#include <iostream>
using namespace std;
int main()
{
int T; //用例数量
cin>>T;
while(T--){
int n,m; //总人数和关系数
cin>>n>>m;
int cd[n]={0}; //出度
int rd[n]={0}; //入度
int zz[n]={0}; //用于记录合格的镇长
for(int k=0;k<m;k++){
int i,j; //每组数据
cin>>i>>j;
if(i==j) continue;
cd[i]+=1;
rd[j]+=1;
}
int count=0; //镇长的数量
for(int k=0;k<n;k++){
if(cd[k]==0&&rd[k]==n-1) zz[count++]=k;
}
cout<<count<<endl;
for(int k=0;k<count;k++){
cout<<zz[k];
if(k!=count-1) cout<<" ";
}
cout<<endl;
}
}
编辑于 2015-08-18 17:23:28
回复(1)
import java.util.ArrayList;
import java.util.Scanner;
/*思路：
* 镇长需要满足的要求：
1、所有人都认识镇长(入度=n-1)
2、镇长不认识任何人(出度=0)
使用2个长度为n的数组，来分别统计每个人的出度和入度。
另外，注意碰到自己认识自己的输入，直接跳过即可。
*/
public class Main{
public static void main(String[] args) {
int T; //数据组数
int n; //镇上的人数
int m; //相互之间的认识关系数
int a;
int b;
int rd[]; //入度(别人认识他)
int cd[]; //出度(他认识别人)
ArrayList<Integer> list; //存放***编号
Scanner reader = new Scanner(System.in);
T = reader.nextInt();
while(T-- > 0){
n = reader.nextInt();
m = reader.nextInt();
rd = new int[n+1]; //初始化数组
cd = new int[n+1];
list = new ArrayList<Integer>();
for(int i=0; i<m; i++){ //遍历关系
a = reader.nextInt();
b = reader.nextInt();
if(a == b){ //自己认识自己
continue; //直接进入下次循环
}
cd[a] ++;
rd[b] ++;
}
for(int i=1; i<=n; i++){ //遍历人数(1-N)
if(cd[i] == 0 && rd[i] == n-1){
list.add(i); //记录***编号
}
}
if(list.isEmpty()){ //没有***
System.out.println(0);
System.out.println();
}else{
System.out.println(list.size());
for(int i=0; i<list.size(); i++){
//注意输出格式
if(i == 0){
System.out.print(list.get(i));
}else{
System.out.print(" "+list.get(i));
}
System.out.println();
}
}
}
}
}
编辑于 2017-03-22 12:39:01
回复(2)
#include <iostream>
using namespace std;
int main()
{
int T;
cin>>T;
int n,m;
int a,b;
while(T-->0)
{
cin>>n>>m;
int *man_a =new int[n];
int *man_b =new int[n];
int zhen=0;
for(int i=0; i<n; ++i)man_b[i]=man_a[i]=0;
while(m-->0)
{
cin>>a>>b;
if(a!=b)
{
man_a[a-1]++;
man_b[b-1]++;
}
}
for(int i=0; i<n; ++i)
{
if(man_a[i] == 0 && man_b[i]==n-1)
{
zhen = i+1;
break;
}
}
if(zhen>0)
{
cout<<1<<endl;
cout<<zhen;
}
else cout<<0<<endl;
cout<<endl;
delete []man_a;
delete []man_b;
}
return 0;
}
感觉最坑的是输出格式比如最后的换行，还有期中隐藏的陷阱比如根本不可能有多个镇长
编辑于 2015-08-19 15:18:10
回复(0)
首先，说说思路：
360笔试的时候，一直提示超出内存限制，过了笔试之后，仔细审题，才明白了原因。我在笔试的时候，用了二维数组，用二维数组去存储两个人之间的关系，这样人很多的时候，当然会超过内存限制啊！！！
存储人与人之间的关系，一定要用二维数组吗？
再仔细读题，成为镇长的条件是：别人都认识他，然而他不认识别人。这样，如果A为镇长，则认识他的关系数必为n-1（这里的n为人数）。
而且输入的时候，输入了几组人与人之间的认识情况：Ai Bi（Ai认识Bi）
设想我们是不是只用一个数组表示这些认识与被认识的关系，代码中用relations[i]存取，认识自己则i++，自己认识别人则i--，即处理一条人数关系如下：
relations[Ai--];
relations[Bi++];
由此再遍历relations[]数组，判断处理即可。
下面是代码：
360笔试的时候，一直提示超出内存限制，过了笔试之后，仔细审题，才明白了原因。我在笔试的时候，用了二维数组，用二维数组去存储两个人之间的关系，这样人很多的时候，当然会超过内存限制啊！！！
存储人与人之间的关系，一定要用二维数组吗？
再仔细读题，成为镇长的条件是：别人都认识他，然而他不认识别人。这样，如果A为镇长，则认识他的关系数必为n-1（这里的n为人数）。
而且输入的时候，输入了几组人与人之间的认识情况：Ai Bi（Ai认识Bi）
设想我们是不是只用一个数组表示这些认识与被认识的关系，代码中用relations[i]存取，认识自己则i++，自己认识别人则i--，即处理一条人数关系如下：
relations[Ai--];
relations[Bi++];
由此再遍历relations[]数组，判断处理即可。
下面是代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 关键在于relations[]数组的存取，并不一定使用二维数组啊
*/
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int T = scn.nextInt(); // 测试数据组数
for (int i = 0; i < T; i++) {
int n = scn.nextInt(); // 人数
int m = scn.nextInt(); // 关系数
boolean isOffical = true;
// 存在镇长，首先至少要有n-1条关系，因为至少要有n-1个人都认识同一个人
if (m < n - 1) {
System.out.println(0);
System.out.println();
isOffical = false;
}
int[] relations = new int[n + 1]; // 存取这n个人对应的认识关系数，别人认识自己的个数-自己认识别人的个数
for (int j = 0; j < m; j++) {
// out表示自己认识别人
int out = scn.nextInt();
// in表示别人认识自己
int in = scn.nextInt();
if (isOffical) {
if (out != in) {
relations[out]--;
relations[in]++;
}
}
}
if (!isOffical) { // 该组不存在镇长
continue;
}
// 存储符合条件的镇长
List<Integer> list = new ArrayList<Integer>();
for (int j = 1; j < relations.length; j++) {
if (relations[j] == n - 1) {
list.add(j);
}
}
System.out.println(list.size());
if (list.size() != 0) {
for (int j = 0; j < list.size() - 1; j++) {
System.out.print(list.get(j) + " ");
}
System.out.print(list.get(list.size()-1)); // 最后一个输出没有空格
}
System.out.println();
}
scn.close();
}
}
发表于 2015-08-18 17:58:27
回复(0)
时间复杂度：O（n）;空间复杂度：O(n).
voidInitSxhN(){
intt=0;
cin>>t;
while(t--){
intn,m;
inta,b;
cin>>n>>m;
if(1== n){ //镇中只有一人，直接输出
printf("1\n1\n");
if(m)cin>>a>>b;
}
elseif(0== m){ //关系未给出
printf("0\n\n");
}
else{
vector <int> man(n,1); //镇中所有人：：>=0:认识他的人数；=-1:他认识其他人
vector <int> hxr; //保存***
while(m--){
scanf("%d%d",&a,&b);
if(a == b); //自己认识自己，初始化时已加入
else{
man[a-1] = -1; //认识其他人
if(-1!= man[b-1]){ //不认识其他人时，人数加1
++man[b-1];
}
}
}
for(inti=0;i<n;++i){
if(n == man[i]){ //挑选出***
hxr.push_back(i+1);
}
}
m = hxr.size();
printf("%d\n",m);
for(inti=0;i<m;i++){ //输出***
if(i)printf(" ");
printf("%d",hxr[i]);
}
printf("\n");
}
}
}
编辑于 2015-08-12 14:19:25
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int MAX=100000;
int indeg[MAX+10],outdeg[MAX+10];
int main()
{ int T,n,m; int a,b; cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) indeg[i] = outdeg[i] = 0; for(int i=0;i<m;i++) { cin>>a>>b; if(a != b) { outdeg[a]++; indeg[b]++; } } int result=0; for(int i=1;i<=n;i++) { if(indeg[i]==n-1 && outdeg[i]==0) { result = i; break; } } if(result == 0) printf("0\n\n"); else printf("1\n%d\n", result); } return 0;
}
发表于 2017-12-08 03:03:40
回复(0)
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)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<int> rd(n);
vector<int> cd(n);
for(int i=0;i<m;i++)
{
int p,q;
cin>>p>>q;
if(p==q)
continue;
cd[p-1]++;
rd[q-1]++;
}
vector<int> cap;
for(int i=0;i<n;i++)
{
if(cd[i]==0&&rd[i]==n-1)
cap.push_back(i+1);
}
cout<<cap.size()<<endl;
for(int i=0;i<cap.size();i++)
{
if(i<cap.size()-1)
cout<<cap[i]<<" ";
cout<<cap[cap.size()-1];
}
cout<<endl;
}
return 0;
}
发表于 2017-07-13 11:33:23
回复(0)
使用一个数组即可存储信息：如果某人认识其他任何一个人，这个人排除当镇长的可能性；如果所有人中有多于一个人不认识其他人，那么没有镇长。另外，由于只有是或者不是两个可能性，使用位图就可以节省很大内存空间。
#include <iostream>
#include <memory.h>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int n, m;
cin >> n >> m;
int *arr = new int[n + 1];
memset(arr, 0, (n + 1) * sizeof(int));
while (m--)
{
int ai, bi;
cin >> ai >> bi;
if (ai == bi)
continue ;
arr[ai] = -1;
}
int count = 0;
int result = 0;
for (int i = 1; i < n + 1; i++)
{
if (arr[i] == 0)
{
if (count >= 1)
{
result = 0;
break;
}
count++;
result = i;
}
}
if (result == 0)
cout << 0 << endl << endl;
else
cout << 1 << endl << result <<
endl;
delete[] arr;
}
return 0;
}
发表于 2017-03-15 17:35:45
回复(0)
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> degree(n,make_pair(0,0));
while(m--)
{
int a,b;
cin>>a>>b;
if(a!=b)
{
degree[a-1].first++;
degree[b-1].second++;
}
}
int count=0;
vector<int> ans;
for(int i = 0;i<degree.size();i++)
{
if(degree[i].first == 0 && degree[i].second == n-1)
{ count++;ans.push_back(i+1);}
}
cout<<count<<endl;
if(ans.size() == 0)cout<<endl;
else
{
for(int i=0;i<ans.size();i++)
{
if(ans.size()-1 == i)cout<<ans[i]<<endl;
else cout<<ans[i]<<" ";
}
}
}
return 0;
}
发表于 2016-09-06 10:18:46
回复(0)
图中点的入度和出度的问题，一个人不认识其他人，则出度为0，自环不考虑加一个判断过滤即可。其他人都认识他，则入度为n-1。定义两个数组存每个点的出度和入度，然后再判断就可以得到答案。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
const int maxn = 100005;
int main()
{
int T;
int n, m;
scanf("%d", &T);
while(T --){
scanf("%d%d", &n, &m);
vector<int> ind(n + 1, 0);
vector<int> outd(n + 1, 0);
int u, v;
while(m --){
scanf("%d%d", &u, &v);
if(u == v) continue;
ind[v] ++;
outd[u] ++;
}
int index = -1;
for(int i = 1; i <= n; ++ i){
if(ind[i] == n - 1 && outd[i] == 0){
index = i;
break;
}
}
if(index == -1){
printf("0\n\n");
}
else {
printf("1\n%d\n", index);
}
}
return 0;
}
发表于 2016-04-06 11:45:54
回复(0)
不知道为什么提示“运行错误:请检查是否存在数组越界非法访问，野指针乱访问，空指针乱访问等情况”
import java.util.Scanner; public class Main { /** * 题目： * 找出别人都认识他，而他其他人都不认识的人 * 输入： * T T个这样的测试样例 * n m n个人 m个关系数 * 下面m行就是关系数 * 输出： * 第一行：这样的人有几个 * 满足条件人的编号 * * 若不存在，输出 0 空格 */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner scn = new Scanner(System.in); int T = scn.nextInt(); // 测试数据组数 while((T--)>0) { int n = scn.nextInt(); // 人数 int m = scn.nextInt(); // 关系数 if(n == 1){ System.out.print(1+"\n"+1); continue; } if(m<n-1){ System.out.print(0+"\n"+0); continue; } // 认识人的数量 int[] A = new int[n+1]; // 被认识的数量 int[] B = new int[n+1]; // m1 认识 m2 for(int k =0;k<m;k++){ int m1 = scn.nextInt(); int m2 = scn.nextInt(); if(m1!=m2){ // m1 认识的人数 去除自己的情况 A[m1]++; //m2 被多少人认识，去除自己的情况 B[m2]++; } } // 自己认识自己的情况可以不用考虑，A[i] = 0 表示 i 不认识除自己以外的其他人， B[i] = n-1 表示i 其他人都认识 int id = -1; for(int kk = 1;kk<=n;kk++){ if(A[kk]==0 && B[kk]==n-1){ id = kk; break; } } if(id == -1){ System.out.print("0\n\n"); }else{ System.out.print(1+"\n"+id+"\n"); } } } }
发表于 2016-03-14 19:27:58
回复(0)
#include<iostream>
using namespace std;
int main(){
int T;
int n,m,a,b;
cin>>T;
while(T--){
cin>>n>>m;
if(n==1){
cout<<1<<endl;
cout<<1<<endl;
}
int in[1000000]={0};
int out[1000000]={0};
for(int i=1;i<=m;i++){
cin>>a>>b;
if(a!=b){
in[b-1]++;
out[a-1]++;
}
}
int goal=0;
for(int i=0;i<n;i++){
if(in[i]==n-1&&out[i]==0)
{goal=i+1;break;}
}
if(goal==0){
cout<<0<<endl;
cout<<endl;
}
else{
cout<<1<<endl;
cout<<goal<<endl;
}
}
return 0;
}
哪里出错了，为什么通不过用例8 12
发表于 2015-09-24 22:38:02
回复(0)
import java.util.*;
public class Main{
public static void main(String []args){
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
sc.nextLine();
for(int i = 0;i<count;i++){
String[] s1 = sc.nextLine().split(" ");
int peopleNum = Integer.valueOf(s1[0]);
int[] people = new int[peopleNum];
int max = Integer.valueOf(s1[1]);
for(int j =0;j<max;j++){
String[] s2 = sc.nextLine().split(" ");
int p1 = Integer.valueOf(s2[0])-1;
int p2 = Integer.valueOf(s2[1])-1;
people[p1]--;
people[p2]++;
}
String result = "";
int c = 0;
for(int j = 0;j<peopleNum;j++){
if(people[j]==peopleNum-1){
result += String.valueOf(j+1);
c++;
}
}
System.out.println(c);
System.out.println(result);
}
}
}
发表于 2019-08-02 19:20:13
回复(0)
题目没看懂，看了代码之后明白了
首先输入num为多少个测数组，也就是多少个城镇，之后第一行，n，m分别为为城镇的人数，城镇的关系数，之后有m行关系数组，测试数据有三个城镇，就有三个输出。
通过konw和be_konw记录认识多少人，和被多少认识。
while True:
try:
num = int(input())
for _ in range(num):
n,m = map(int, input().split())
know = [0]*n
be_know=[0]*n
for _ in range(m):
relate = list(map(int,input().split()))
if relate[0] != relate[1]:
know[relate[0]-1] += 1
be_know[relate[1]-1] += 1
for i in range(n):
if be_know[i]==n-1 and know[i] == 0:
print(1)
print(i+1)
break
else:
print(0)
print('')
except:break
发表于 2019-07-16 12:08:54
回复(0)
借鉴各位大佬的解答，还是磕磕绊绊写了好久。。。
只有两种情况：
1、1位镇长及其编号
2、没有合适的
全都在最后输出的时候判断，不需要在一开始就对m分类判断
#include<iostream>using namespace std;int main() { int T;//数据组数 cin>>T; while(T--) { int n,m;//总人数、关系数 cin>>n>>m; int cd[n+1];//出度，记录每个人认识几个人 int rd[n+1];//入度 for(int i=1;i<=n;i++) { cd[i]=0; rd[i]=0; } for(int k=0;k<m;k++) { int i,j; cin>>i>>j; if(i==j) continue; cd[i]+=1; rd[j]+=1; } int count=0; for(int k=1;k<=n;k++) { if((cd[k]==0)&&(rd[k]==n-1)) { count=k; break; } } if(count==0) { cout<<0<<endl; cout<<endl; } else { cout<<1<<endl; cout<<count<<endl; } } return 0; }
发表于 2019-04-11 20:53:48
回复(0)
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)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int main(){
int T;//数据组数
while(cin>>T){
for(int i=0;i<T;++i){
int n;//镇子上的人数
int m;//相互之间的关系数目
cin>>n>>m;
int numi=0;
vector<int> IDArray;
if(n==1&&m==0){
numi=1;
IDArray.push_back(numi);
}else if(n>1&&m==0){
//do nothing;
}else{
vector<pair<int,int>> relationMap;
//依次录入关系对
for(int j=0;j<m;++j){
int startID;
int endID;
cin>>startID>>endID;
relationMap.emplace_back(make_pair(startID,endID));
}
//结点的入队数组
int inArray[n+1];
memset(inArray,0,sizeof(inArray));
//结点的出队数组
int outArray[n+1];
memset(outArray,0,sizeof(outArray));
for(pair<int,int> curPair:relationMap){
if(curPair.first!=curPair.second){
inArray[curPair.second]++;
outArray[curPair.first]++;
}
}
for(int i=1;i<=n;++i){
if(inArray[i]==n-1&&outArray[i]==0){
numi++;
IDArray.push_back(i);
}
}
}//else
std::cout<<numi<<std::endl;
if(!numi)
std::cout<<std::endl;
else{
for(int ID:IDArray)
std::cout<<ID<<std::endl;
}
}
}
return 0;
}
发表于 2018-08-19 22:34:07
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
#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; }