前言

上次集训赛（周三）刷到一个特别有意思的题，关于图论的。当时没刷多少图论的题目，所以图论算法这块一直都挺畏惧的hhh~~，但这个题目让我重新认识到有的图论原来并不难，只是披着羊皮的狼，这个题目我是用 map 映射做的，今天想起才来写个关于它的题解，题目链接放在后面。

题目大意&链接

本题要求找出图中邻居颜色多样性最大的顶点颜色。具体来说，对于颜色 k，需统计所有属于颜色 k 的顶点的邻居颜色集合的大小（去重），最终输出该值最大的颜色（若有多个，选数值最小的）。

输入输出样例：
输入：

6 6
1 1 2 3 5 8
1 2
3 2
1 4
4 3
4 5
4 6

输出：

3

详情：cf_246D

解题思路

输入处理与颜色去重：用数组 s 存储所有唯一颜色，用数组 flagc 标记颜色是否已存在，确保数组 s 中颜色唯一。

int idx = 0;
for (int i = 1; i <= n; i++) {
    cin >> c[i];
    if (!flagc[c[i]]) //去重
        s[++idx] = c[i], flagc[c[i]] = 1;
}

统计邻居颜色多样性：遍历每条边，若边两端顶点颜色不同，用 map<pair<int, int>, bool> 记录颜色对 (c[x], c[y])，避免重复统计。每遇到新的颜色对，对应颜色的多样性计数数组 cntc 加 1

while (m--) {
    int x, y;
    cin >> x >> y;

    if (c[x] == c[y]) continue;

    if (!flag[{c[x], c[y]}]) cntc[c[x]]++, flag[{c[x], c[y]}] = 1;

    if (!flag[{c[y], c[x]}]) cntc[c[y]]++, flag[{c[y], c[x]}] = 1;
}

寻找最优颜色：对唯一颜色数组 s 排序，遍历 s，找到 cntc 最大的颜色，若有多个，选排序后第一个出现的。

sort(s + 1, s + 1 + idx);

int max_cnt = 0, ans = s[1];
for (int i = 1; i <= idx; i++) {
    if (cntc[s[i]] > max_cnt) {
        // 找到最大多样性的颜色
        max_cnt = cntc[s[i]], ans = s[i];
    }
}

AC代码附上

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int n, m;
int c[100010], s[100010], cntc[100010];
bool flagc[100010];

map<pair<int, int>, bool> flag;

int main() {
    cin >> n >> m;

    int idx = 0;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        if (!flagc[c[i]]) //去重
            s[++idx] = c[i], flagc[c[i]] = 1;
    }

    while (m--) {
        int x, y;
        cin >> x >> y;

        if (c[x] == c[y]) continue;

        if (!flag[{c[x], c[y]}]) cntc[c[x]]++, flag[{c[x], c[y]}] = 1;

        if (!flag[{c[y], c[x]}]) cntc[c[y]]++, flag[{c[y], c[x]}] = 1;
    }

    sort(s + 1, s + 1 + idx);

    int max_cnt = 0, ans = s[1];
    for (int i = 1; i <= idx; i++) {
        if (cntc[s[i]] > max_cnt) {
            // 找到最大多样性的颜色
            max_cnt = cntc[s[i]], ans = s[i];
        }
    }

    cout << ans;
    return 0;
}