大型植被恢复

题目

链接：1684. 大型植被恢复 - AcWing题库

长时间的干旱使得 Farmer John 的 NN 块草地上牧草匮乏。

随着雨季即将到来，现在应当是重新种植的时候了。

在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。

他想要在每块草地上播种其中一种草。

作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。

他的 MM 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。

已知每块草地最多被 44 头奶牛喜爱。

请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。

输入格式

输入的第一行包含 NN 和 MM。

以下 MM 行，每行包含两个范围为 1…N1…N 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。

输出格式

输出一个 NN 位数，每一位均为 1…41…4 之一，表示每一块草地上所种的草的种类。

第一位对应草地 11 的草的种类，第二位对应草地 22，以此类推。

如果有多种可行的解，只需输出所有解中最小的 NN 位数。

数据范围

2≤N≤1002≤N≤100,
1≤M≤150

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, m;
    static int[][] a = new int[110][110];
    static int[] ans = new int[110];
    static boolean[] f = new boolean[5];
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        m = inScanner.nextInt();
        for(int i = 1; i <= m; i ++)
        {
            int x, y;
            x = inScanner.nextInt();
            y = inScanner.nextInt();
            a[x][y] = 1;
            a[y][x] = 1;
        }
        for(int i = 1; i <= n; i ++)
        {
            Arrays.fill(f, false);
            for(int j = 1; j <= n; j ++)
            {
                if(a[i][j] == 1)
                    f[ans[j]] = true;
            }
            for(int j = 1; j <= 4; j ++)
            {
                if(!f[j])
                {
                    ans[i] = j;
                    break;
                }
            }
        }
        for(int i = 1; i <= n; i ++)
            System.out.print(ans[i]);
    }
}