题解 | 挑选镇长

解题思路

我们需要找到一个镇长候选人，满足以下条件：

所有人都认识这个候选人。
这个候选人不认识其他任何人（除了自己）。

为了解决这个问题，我们可以使用图的概念：

将每个人视为图中的一个节点。
将“认识”关系视为有向边。

算法步骤：

构建图：使用两个数组cd和rd来记录每个人的出度和入度。
统计入度和出度：
- 遍历每个认识关系，更新出度和入度。
寻找候选人：
- 遍历每个人，找到出度为0且入度为n-1的候选人。

代码

cpp
java
python

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;  // 用例数量
    cin >> T;

    while (T--) {
        int n, m;  // 总人数和关系数
        cin >> n >> m;

        vector<int> outDegree(n + 1, 0);  // 出度
        vector<int> inDegree(n + 1, 0);   // 入度
        vector<int> candidates;             // 用于记录合格的镇长

        for (int k = 0; k < m; k++) {
            int i, j;  // 每组数据
            cin >> i >> j;
            if (i != j) {  // 忽略自我认识的情况
                outDegree[i]++;
                inDegree[j]++;
            }
        }

        for (int k = 1; k <= n; k++) {  // 从1到n遍历
            if (outDegree[k] == 0 && inDegree[k] == n - 1) {
                candidates.push_back(k);  // 记录合格的镇长
            }
        }

        cout << candidates.size() << endl;  // 输出镇长的数量
        for (size_t k = 0; k < candidates.size(); k++) {
            cout << candidates[k];
            if (k != candidates.size() - 1) cout << " ";  // 输出时添加空格
        }
        cout << endl;  // 换行
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] outDegree = new int[n + 1];  // 出度
            int[] inDegree = new int[n + 1];   // 入度
            List<Integer> candidates = new ArrayList<>();  // 用于记录合格的镇长

            for (int k = 0; k < m; k++) {
                int i = sc.nextInt();
                int j = sc.nextInt();
                if (i != j) {  // 忽略自我认识的情况
                    outDegree[i]++;
                    inDegree[j]++;
                }
            }

            for (int k = 1; k <= n; k++) {  // 从1到n遍历
                if (outDegree[k] == 0 && inDegree[k] == n - 1) {
                    candidates.add(k);  // 记录合格的镇长
                }
            }

            System.out.println(candidates.size());  // 输出镇长的数量
            for (int k = 0; k < candidates.size(); k++) {
                System.out.print(candidates.get(k));
                if (k != candidates.size() - 1) System.out.print(" ");  // 输出时添加空格
            }
            System.out.println();  // 换行
        }
        sc.close();
    }
}

def find_mayor_candidates():
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    
    index = 0
    T = int(data[index])
    index += 1
    results = []
    
    for _ in range(T):
        n, m = map(int, data[index].split())
        index += 1
        
        out_degree = [0] * (n + 1)  # 出度
        in_degree = [0] * (n + 1)   # 入度
        candidates = []              # 用于记录合格的镇长
        
        for __ in range(m):
            i, j = map(int, data[index].split())
            index += 1
            if i != j:  # 忽略自我认识的情况
                out_degree[i] += 1
                in_degree[j] += 1
        
        for k in range(1, n + 1):  # 从1到n遍历
            if out_degree[k] == 0 and in_degree[k] == n - 1:
                candidates.append(k)  # 记录合格的镇长
        
        results.append(f"{len(candidates)}")
        if candidates:
            results.append(" ".join(map(str, candidates)))
        else:
            results.append("")
    
    print("\n".join(results))

if __name__ == "__main__":
    find_mayor_candidates()

算法及复杂度

算法：图的入度和出度统计
时间复杂度： $\mathcal{O(n + m)}$ ，遍历所有关系和所有人
空间复杂度： $\mathcal{O(n)}$ ，存储入度和出度数组