简单染色问题：不邻接植花

红太狼 2023-10-06 09:06 3阅读 0赞

## 简单染色问题：不邻接植花 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路： ####

对图中的节点建立邻接表，设解向量的初值均为0，即均未染色，使用容器set存储4种颜色

按顺序遍历图中的所有节点，在set中去除所有该节点的邻接表中节点已用过的颜色（ erase(key\_value) 删除键值为key\_value的值 ），将set中的第一种颜色赋给该节点

处理完所有节点后，返回解向量

#### 代码： ####

class Solution {
        
    public:
        vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) {
        
            vector<vector<int>> table;
            int i,j;
            for( i=0;i<N;i++ )
            {
        
                table.push_back( vector<int>() );
            }
            for( i=0;i<paths.size();i++ )
            {
        
                table[ paths[i][0]-1 ].push_back( paths[i][1]-1 );
                table[ paths[i][1]-1 ].push_back( paths[i][0]-1 );
            }
            vector<int> ans(N,0);
            for( i=0;i<N;i++ )
            {
        
                set<int> color={
        1,2,3,4};
                for( j=0;j<table[i].size();j++ )
                {
        
                    color.erase( ans[ table[i][j] ] );
                }
                ans[i]=*color.begin();
            }
            return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200519213330930.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200519213347998.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70