C++ 使每个节点都有一个已染色的邻居节点，需要染色的最少节点数量

在这个问题中，我们将染色图中的最少节点，使得图中的每个节点与最远距离为1的一个已染色节点相邻。

最小化染色节点数量的简单逻辑是，要么染色奇数距离的节点，要么染色偶数距离的节点。因此，我们可以染色交替的节点，并且对于每个节点，我们可以找到一个最远距离为1的已染色节点。

问题陈述 - 给定一个包含N个节点和E条边的图。已知我们最多可以染色floor(N/2)个节点。我们需要找出要染色的最少节点数量，使得图中的每个节点的距离最大为1单位的染色节点。

注意 - 两个节点之间的距离为1单位。

示例示范

输入

1 -> 4, 1 -> 3, 4 -> 5, 4 -> 2

输出

4,3

解释 − 这是图表的可视化。

因此，如果我们给4和3节点上色，我们可以使每个节点的着色节点最多相隔1个距离。

输入

1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5

输出

解释 − 由于图中的所有节点都与1相连。如果我们对1进行染色，我们可以得到所需的结果。

方法

这种方法将使用映射数据结构存储访问过的节点。同时，我们将使用列表存储源节点到偶数距离和奇数距离的节点。最后，如果我们发现偶数距离的节点较少，我们将打印该节点。否则，我们将打印奇数距离的节点。

步骤

第1步 − 定义“visited”映射全局变量。同时，定义全局“odd_list”和“even_list”列表来存储偶数距离的节点。

第2步 − 在performBFS()函数中，将“head”初始化为1，并定义队列来存储距离和节点的配对。

第3步 − 将头部与距离0插入队列，并更新visited[head]为1。

第4步 − 遍历队列。

第4.1步 − 从队列中取出第一个配对。

第4.2步 − 如果距离是奇数，将节点插入“odd_list”列表。

第4.3步 − 否则，将节点插入“even_list”列表。

第4.4步 − 遍历当前节点的所有邻居节点。如果当前节点未被访问，则通过将距离增加1将其插入队列。同时，更新visited[p]为1。

第4.5步 − 在main()方法中，如果even_list的大小较小，则打印even_list的所有元素。否则，打印odd_list的所有元素。

示例

#include <bits/stdc++.h>
using namespace std;

// For storing the graph
map<int, vector<int>> grp;
// Stores the visited nodes
map<int, int> visited;
// To store nodes that are at odd and even distances from the root node
vector<int> odd_dist;
vector<int> even_dist;
void performBFS() {
    int head = 1;
    queue<pair<int, int>> que;
    // Add head node to queue
    que.push({head, 0});
    visited[head] = 1;
    while (!que.empty()) {
        // Get first noed
        int node = que.front().first;
        int dist = que.front().second;
        que.pop();
        // For odd distance
        if (dist & 1) {
            odd_dist.push_back(node);
        }
        // For even distance
        else {
            even_dist.push_back(node);
        }
        // Traverse neighbor nodes
        for (auto p : grp[node]) {
            // Get unvisited nodes
            if (!visited.count(p)) {
                que.push({p, (dist + 1)});
                visited[p] = 1;
            }
        }
    }
}
int main() {
    grp[1].push_back(4);
    grp[4].push_back(1);
    grp[2].push_back(4);
    grp[4].push_back(2);
    grp[3].push_back(1);
    grp[1].push_back(3);
    grp[4].push_back(5);
    grp[5].push_back(4);
    performBFS();
    cout << "The nodes we should color is ";
    // Print nodes at odd or even distances according to the total number of nodes
    if (odd_dist.size() < even_dist.size()) {
        for (int p : odd_dist) {
            cout << p << " ";
        }
    } else {
        for (int p : even_dist) {
            cout << p << " ";
        }
    }
    return 0;
}