大型植被恢复
问题描述
长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。
随着雨季即将到来，现在应当是重新种植的时候了。
在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。
他想要在每块草地上播种其中一种草。
作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。
他的 M 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。
已知每块草地最多被 3 头奶牛喜爱。
请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
输入格式
输入的第一行包含 N 和 M。
以下 M 行，每行包含两个范围为 1…N 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。
输出格式
输出一个 N 位数，每一位均为 1…4 之一，表示每一块草地上所种的草的种类。
第一位对应草地 1 的草的种类，第二位对应草地 2，以此类推。
如果有多种可行的解，只需输出所有解中最小的 N 位数。
数据范围
2≤N≤100,
1≤M≤150
输入样例：
5 6
4 1
4 2
4 3
2 5
1 2
1 5
输出样例：
12133
思路分析
染色问题
完整代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 110;
int g[N][N];
bool st[5];
int res[N];
int main()
{
scanf("%d%d", &n, &m);
while(m--)
{
int i, j;
scanf("%d%d", &i, &j);
g[i][j] = g[j][i] = 1;
}
res[1] = 1;
for(int i = 2; i <= n; i++)
{
memset(st, 0, sizeof st);
for(int j = 1; j < i; j++)
{
if(g[i][j] == 1)
{
st[res[j]] = 1;
}
}
for(int j = 1; j <= 4; j++)
{
if(st[j] == 0)
{
res[i] = j; //能取 不要继续进行了 更新答案
break;
}
}
}
for(int i = 1; i <= n; i++)
{
printf("%d", res[i]);
}
return 0;
}