I题营养需求

长时间的干旱使得Farmer John的N块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。
在Farmer John的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农，Farmer John想要确保他的每头奶牛都能得到丰富的食谱。他的M头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John知道没有一块草地受到多于3头奶牛的喜爱。
请帮助Farmer John选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
输入描述:
输入的第一行包含N（2≤N≤100）和M（1≤M≤150）。以下M行，每行包含两个范围为1…N的整数，为Farmer John的一头奶牛喜欢的两块草地。
输出描述:
输出一个N位数，每一位均为1…4之一，表示每一块草地上所种的草的种类。第一位对应草地1的草的种类，第二位对应草地2，以此类推。如果有多种可行的解，只需输出所有解中最小的N位数。
示例1
输入

复制
5 6
4 1
4 2
4 3
2 5
1 2
1 5
输出

复制
12133
备注:
2≤N≤100 1≤M≤150

其他数均在[1,N]内
解答
分析了一下题意，可以把草地看成点，把每头牛喜欢的两个草地看成这两点之间有一条边，两草地之间有边的话，这两个草地颜色要不一样，因为颜色只有4种，所以可以开一个标记数组f[5]存储出现过的颜色。
题意要求最小的N位数。
1.那么第一块草地必定放1。
2.第2块草地要看与第一块草地之间有没有边（即有头牛喜欢草地1， 2）有边的话标记1中放的颜色，然后for一遍找到最小的且没被标记的颜***r>....
3.第x块草地放的草种类型，先标记一遍在[1, x - 1]草地中出现过的草种，然后同上，为啥只要标记[1, x - 1], 因为题意要求最小N位数，那么要求的第x位数要最小，那 x 就只与在其的x - 1位有关系, 其后的不用考虑了
标记代码如下

 memset(ee, 0, sizeof ee);//重置标记数组
         for (int j = 1; j < i; ++j) {//遍历[1, i - 1]
            if (f[i][j] > 0 ) ee[an[j]] = 1;//有边就标记其草种类型
        }

第i位最小草种如下

 for (int j = 1; j <= 4; ++j) {//找到最小的且没被标记的草种
            if (ee[j] == 0) {
                res = j;
                //cout << i << endl;
                break;
            }
        }
        an[i] = res;

参考代码如下

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[160][160];
int an[160];
int ee[10];
int main()
{
    cin >> n >> m;
    int u, v;
    while (m--) {
        cin >> u >> v;
        f[u][v] = 1;
        f[v][u] = 1;
    }
    an[1] = 1;
    for (int i = 2; i <= n; ++i) {
        int res = 0;
        memset(ee, 0, sizeof ee);
        for (int j = 1; j < i; ++j) {
            if (f[i][j] > 0 ) ee[an[j]] = 1;
        }
        for (int j = 1; j <= 4; ++j) {
            if (ee[j] == 0) {
                res = j;
                //cout << i << endl;
                break;
            }
        }
        an[i] = res;
    }
    for (int i = 1; i <= n; ++i) {
        cout << an[i];
    }
    return 0;
}