图中着色的最小节点数，使得每个节点都具有一个着色的邻居节点

---

在这个问题中，我们将对图的最小节点进行着色，以便图的每个节点都具有最大距离为 1 的着色节点。

最小化着色节点数量的简单逻辑是：要么对奇数距离处的节点着色，要么对偶数距离处的节点着色。因此，我们可以对交替节点着色，并且对于每个节点，我们最多可以在距离 1 处拥有一个着色节点。

问题陈述 - 我们给定了一个包含 N 个节点和 E 条边的图。给定我们最多可以对 floor(N/2) 个节点着色。我们需要找到要着色的最小节点数，以便图的每个节点都具有最多距离 1 个单位的着色节点。

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

示例

输入

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

输出

4,3

解释 - 以下是图的可视化。

              1
            /    \ 
           4      3 
          /  \ 
         2    5

因此，如果我们对节点 4 和 3 着色，我们可以为每个节点获得最多距离 1 的着色节点。

输入

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

输出

1

解释 - 由于图的所有节点都连接到 1。如果我们对 1 着色，我们可以获得所需的结果。

方法

此方法将使用 map 数据结构来存储已访问的节点。此外，我们将使用列表来存储从源节点到偶数和奇数距离的节点。最后，如果我们在偶数距离处找到较少的节点，我们将打印该节点。否则，我们将打印位于奇数距离处的节点。

算法

步骤 1 - 定义全局变量 'visited' map。此外，定义全局 'odd_list' 和 'even_list' 列表以存储偶数距离处的节点。

步骤 2 - 在 performBFS() 函数中，将 'head' 初始化为 1，并定义队列以存储距离和节点对。

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

步骤 4 - 遍历队列。

步骤 4.1 - 从队列中获取第一对。

步骤 4.2 - 如果距离为奇数，则将节点插入 'odd_dist' 列表。

步骤 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;
}

输出

The nodes we should color is 4 3

时间复杂度 - 遍历所有节点的 O(N)。

空间复杂度 - 在队列中存储节点的 O(N)。

我们使用 BFS 遍历访问给定图的每个节点。此外，我们跟踪每个节点到源节点的距离，以过滤偶数距离处的节点和奇数距离处的节点。