题目描述：
长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。
随着雨季即将到来，现在应当是重新种植的时候了。
在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。
他想要在每块草地上播种其中一种草。
作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。
他的 MM 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。
已知每块草地最多被 3 头奶牛喜爱。
请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
输入格式
输入的第一行包含 N 和 M。
以下 M 行，每行包含两个范围为 $ 1\cdots N $ 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。
输出格式
输出一个 N 位数，每一位均为 $ 1\cdots 4 $ 之一，表示每一块草地上所种的草的种类。
第一位对应草地 1 的草的种类，第二位对应草地 2，以此类推。
如果有多种可行的解，只需输出所有解中最小的 N 位数。
数据范围
输入样例：
1
2
3
4
5
6
7
| 5 6
4 1
4 2
4 3
2 5
1 2
1 5
|
输出样例：
题解：
注意因为每个点最多只能连 3 条边，因此不论怎么染色，肯定存在合法方案（因为颜色数有四种）。可以直接从 1 号点贪心染色，不会出现回溯的情况，直接暴力就行。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<int> g[maxn];
bool vis[maxn][5];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++)
{
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= 4; j++)
{
if (vis[i][j])
continue;
cout << j;
for (auto x : g[i])
{
vis[x][j] = true;
}
break;
}
}
return 0;
}
|