Pass_02 指令的相关操作

1. 1684. 大型植被恢复
   1. 题目大意：
   2. 思路：
   3. 代码：

1684. 大型植被恢复

题目大意：

有N个点，每个点可以和其他最多3个点连一条边，现在给每个点染色，一共有4种颜色：1234，边相连的2个点颜色不能相同，求字典序最小的染色方法

思路：

从前往后遍历每个点，给它染上第一个能染的色，然后把它相连的点都标记为不能染这个色。由于有4种色，每个点最多连3条边，所以一定有一个色可以染

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 310;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N][5];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

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

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= 4; j ++ )
            if (!st[i][j])
            {
                cout << j;
                for (int u = h[i]; ~u; u = ne[u])
                    st[e[u]][j] = true;
                break;
            }

    return 0;
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com