算法小题（五）：选举镇长

灰太狼 2022-05-12 12:44 131阅读 0赞

## 选举镇长：反向朋友圈问题 ##

来源：18年QiHu360秋招笔试题

原题目为：

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

### 输入描述与输出描述： ###

/\*\*  
 \* 选镇长,  
 \* input:   数据组数T---------------------------- 1行  
 \*             本组人数n 互相认识关系数m--- 1行  
 \*             A认识B,B认识C,...------------------ m行【注意:可能存在自己认识自己】  
 \*   
 \* output:  分为T组,每组2行  
 \*                 适合人选数--------------1行  
 \*                 编号 编号 编号...-------- 1行【空格相隔】  
 \*/

###  思路： ###

镇长需要满足的要求就是：

1、所有人都认识镇长（入度=n-1）

2、镇长不认识任何人（出度=0）

使用2个长度为n的数组，来分别统计每个人的出度和入度。

另外，注意碰到自己认识自己的输入，直接跳过。

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;
                }
                /*
                 * 存取这n个人对应的认识关系数，别人认识自己的个数-自己认识别人的个数
                 */
                int[] relations = new int[n + 1]; 
                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();
        }
    }

===============================================================

### 来一个传统的朋友圈问题 ###

A与B相识，B与C相识，可以说A与C间接相识

那么ABC组成一个朋友圈，D同学没人认识，D自己一个圈

用户自定义输入每人所认识的人

求：有几个朋友圈

**思路：利用深度优先搜索**

查找朋友圈的算法如下，测试类可自行编写

package Bytedance;
    
    public class FriendsCircle {
    	public void dfs(int[][] M, int[] visited, int i) {
    		for (int j = 0; j < M.length; j++) {
    			if (M[i][j] == 1 && visited[j] == 0) {
    				visited[j] = 1;
    				dfs(M, visited, j);
    			}
    		}
    	}
    
    	public int findCircleNum(int[][] M) {
    		int[] visited = new int[M.length];
    		int count = 0;
    		for (int i = 0; i < M.length; i++) {
    			if (visited[i] == 0) {
    				dfs(M, visited, i);
    				count++;
    			}
    		}
    		return count;
    	}
    }