圖中著色的最小節點數，使得每個節點都具有一個著色的鄰居節點

---

在這個問題中，我們將對圖的最小節點進行著色，以便圖的每個節點都具有最大距離為 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 遍歷訪問給定圖的每個節點。此外，我們跟蹤每個節點到源節點的距離，以過濾偶數距離處的節點和奇數距離處的節點。